Count connected subgraphs with even node sum

61.8% acceptance

May 13, 2026

You are given an undirected graph with n nodes labeled from 0 to n - 1. Node i has a value of nums[i], which is either 0 or 1. The edges of the graph are given by a 2D array edges where edges[i] = [ui, vi] represents an edge between node ui and node vi. For a non-empty subset s of nodes in the graph, we consider the induced subgraph of s generated as follows: We keep only the nodes in s. We keep only the edges whose two endpoints are both in s. Return an integer representing the number of non-empty subsets s of nodes in the graph such that: The induced subgraph of s is connected. The sum of node values in s is even.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn even_sum_subgraphs(nums: Vec<i32>, edges: Vec<Vec<i32>>) -> i32 {
    let n = nums.len();
    let mut adj = vec![0u32; n];
    for e in &edges {
      let u = e[0] as usize;
      let v = e[1] as usize;
      adj[u] |= 1 << v;
      adj[v] |= 1 << u;
    }
    let one_mask: u32 = nums.iter().enumerate()
      .map(|(i, &v)| if v == 1 { 1u32 << i } else { 0 })
      .sum();
    let mut count = 0i32;
    for s in 1u32..(1u32 << n) {
      if (s & one_mask).count_ones() % 2 != 0 { continue; }
      let start = s.trailing_zeros() as usize;
      let mut visited = 1u32 << start;
      let mut frontier = visited;
      while frontier != 0 {
        let mut new_frontier: u32 = 0;
        let mut f = frontier;
        while f != 0 {
          let i = f.trailing_zeros() as usize;
          new_frontier |= adj[i] & s & !visited;
          f &= f - 1;
        }
        visited |= new_frontier;
        frontier = new_frontier;
      }
      if visited == s {
        count += 1;
      }
    }
    count
  }
}