Incremental even weighted cycle queries

51.2% acceptance

Mar 31, 2026

You are given a positive integer n. There is an undirected graph with n nodes labeled from 0 to n - 1. Initially, the graph has no edges. You are also given a 2D integer array edges, where edges[i] = [ui, vi, wi] represents an edge between nodes ui and vi with weight wi. The weight wi is either 0 or 1. Process the edges in edges in the given order. For each edge, add it to the graph only if, after adding it, the sum of the weights of the edges in every cycle in the resulting graph is even. Return an integer denoting the number of edges that are successfully added to the graph.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_edges_added(n: i32, edges: Vec<Vec<i32>>) -> i32 {
    // Add edge only if it doesn't create an odd-weight cycle.
    // This is a weighted Union-Find with parity.
    // Each node has a "parity distance" to its root.
    // When adding edge (u, v, w):
    //   If u and v are in different components: always safe, union them.
    //   If same component: check if parity(u) ^ parity(v) == w.
    //     If yes: cycle is even, safe to add (but it's redundant for the tree, still add).
    //     If no: cycle is odd, don't add.
    
    let n = n as usize;
    let mut parent: Vec<usize> = (0..n).collect();
    let mut rank = vec![0u32; n];
    let mut parity = vec![0u32; n]; // parity from node to parent
    
    fn find(parent: &mut Vec<usize>, parity: &mut Vec<u32>, x: usize) -> (usize, u32) {
      if parent[x] == x {
        return (x, 0);
      }
      let (root, p) = find(parent, parity, parent[x]);
      parity[x] ^= p;
      parent[x] = root;
      (root, parity[x])
    }
    
    let mut count = 0;
    
    for edge in &edges {
      let u = edge[0] as usize;
      let v = edge[1] as usize;
      let w = edge[2] as u32;
      
      let (ru, pu) = find(&mut parent, &mut parity, u);
      let (rv, pv) = find(&mut parent, &mut parity, v);
      
      if ru != rv {
        // Different components, union
        if rank[ru] < rank[rv] {
          parent[ru] = rv;
          parity[ru] = pu ^ pv ^ w;
        } else if rank[ru] > rank[rv] {
          parent[rv] = ru;
          parity[rv] = pu ^ pv ^ w;
        } else {
          parent[rv] = ru;
          parity[rv] = pu ^ pv ^ w;
          rank[ru] += 1;
        }
        count += 1;
      } else {
        // Same component: check if cycle parity is even
        if pu ^ pv == w {
          // Even cycle, safe to add
          count += 1;
        }
        // Odd cycle, skip
      }
    }
    
    count
  }
}