Welcome to Subscribe On Youtube

3910. Count Connected Subgraphs with Even Node Sum

Description

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.

 

Example 1:

Input: nums = [1,0,1], edges = [[0,1],[1,2]]

Output: 2

Explanation:

s connected? sum of node values counted?
[0] Yes 1 No
[1] Yes 0 Yes
[2] Yes 1 No
[0,1] Yes 1 No
[0,2] No, node 0 and node 2 are disconnected. 2 No
[1,2] Yes 1 No
[0,1,2] Yes 2 Yes

Example 2:

Input: nums = [1], edges = []

Output: 0

Explanation:

s connected? sum of node values counted?
[0] Yes 1 No

 

Constraints:

  • 1 <= n == nums.length <= 13
  • nums[i] is 0 or 1.
  • 0 <= edges.length <= n * (n - 1) / 2
  • edges[i] = [ui, vi]
  • 0 <= ui < vi < n
  • All edges are distinct.

Solutions

Solution 1: Bitmask Enumeration + DFS

Notice that the number of nodes in the problem does not exceed $13$, so we can enumerate all non-empty subsets $s$ of nodes. For each subset, we calculate the total sum of node values and check whether its induced subgraph is connected.

Specifically, we can use an integer $sub$ to represent the subset $s$, where the $i$-th bit of $sub$ is $1$ if node $i$ is in the subset, and $0$ otherwise. For each subset, we first compute the sum of its node values. If the sum is odd, we skip this subset; otherwise, we use DFS to check whether the induced subgraph is connected. We can use an integer $vis$ to represent the visited nodes: initially, the $i$-th bit of $vis$ is $1$ if node $i$ is not in the subset, and $0$ if node $i$ is in the subset. We start DFS from any node in subset $s$, visit all its adjacent nodes, and mark visited nodes in $vis$ as $1$. Finally, if all bits in $vis$ are $1$, it means the induced subgraph of subset $s$ is connected, so we increment the answer by $1$.

The time complexity is $O(2^n \times (n + m))$ and the space complexity is $O(n + m)$, where $n$ and $m$ are the number of nodes and edges, respectively.

  • class Solution {
    private int vis;
    private int m;
    private List<Integer>[] g;

    public int evenSumSubgraphs(int[] nums, int[][] edges) {
        int n = nums.length;
        g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int[] e : edges) {
            g[e[0]].add(e[1]);
            g[e[1]].add(e[0]);
        }
        m = (1 << n) - 1;
        int ans = 0;
        for (int sub = 1; sub <= m; sub++) {
            int s = 0;
            for (int i = 0; i < n; i++) {
                if (((sub >> i) & 1) == 1) {
                    s += nums[i];
                }
            }
            if (s % 2 != 0) {
                continue;
            }
            vis = m ^ sub;
            dfs(Integer.numberOfTrailingZeros(sub));
            if (vis == m) {
                ans++;
            }
        }
        return ans;
    }

    private void dfs(int u) {
        vis |= 1 << u;
        for (int v : g[u]) {
            if (((vis >> v) & 1) == 0) {
                dfs(v);
            }
        }
    }
}


  • class Solution {
public:
    int evenSumSubgraphs(vector<int>& nums, vector<vector<int>>& edges) {
        int n = nums.size();
        vector<vector<int>> g(n);
        for (auto& e : edges) {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }
        int m = (1 << n) - 1;
        int ans = 0;
        int vis;

        auto dfs = [&](this auto dfs, int u) -> void {
            vis |= 1 << u;
            for (int v : g[u]) {
                if (((vis >> v) & 1) == 0) {
                    dfs(v);
                }
            }
        };

        for (int sub = 1; sub <= m; sub++) {
            int s = 0;
            for (int i = 0; i < n; i++) {
                if ((sub >> i) & 1) {
                    s += nums[i];
                }
            }
            if (s % 2 != 0) {
                continue;
            }
            vis = m ^ sub;
            dfs(31 - __builtin_clz(sub));
            if (vis == m) {
                ans++;
            }
        }
        return ans;
    }
};


  • class Solution:
    def evenSumSubgraphs(self, nums: list[int], edges: list[list[int]]) -> int:
        n = len(nums)
        g = [[] for _ in range(n)]
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)
        m = (1 << n) - 1
        ans = 0
        for sub in range(1, m + 1):
            s = sum(x for i, x in enumerate(nums) if sub >> i & 1)
            if s % 2:
                continue
            vis = m ^ sub

            def dfs(u: int) -> None:
                nonlocal vis
                vis |= 1 << u
                for v in g[u]:
                    if (vis >> v & 1) == 0:
                        dfs(v)

            dfs(sub.bit_length() - 1)
            if vis == m:
                ans += 1
        return ans


  • func evenSumSubgraphs(nums []int, edges [][]int) int {
	n := len(nums)
	g := make([][]int, n)
	for _, e := range edges {
		g[e[0]] = append(g[e[0]], e[1])
		g[e[1]] = append(g[e[1]], e[0])
	}
	m := (1 << n) - 1
	ans := 0
	var vis int

	var dfs func(int)
	dfs = func(u int) {
		vis |= 1 << u
		for _, v := range g[u] {
			if (vis >> v & 1) == 0 {
				dfs(v)
			}
		}
	}

	for sub := 1; sub <= m; sub++ {
		s := 0
		for i := 0; i < n; i++ {
			if sub>>i&1 == 1 {
				s += nums[i]
			}
		}
		if s%2 != 0 {
			continue
		}
		vis = m ^ sub
		dfs(bits.Len(uint(sub)) - 1)
		if vis == m {
			ans++
		}
	}
	return ans
}


  • function evenSumSubgraphs(nums: number[], edges: number[][]): number {
    const n = nums.length;
    const g: number[][] = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) {
        g[u].push(v);
        g[v].push(u);
    }
    const m = (1 << n) - 1;
    let ans = 0;
    let vis = 0;

    const dfs = (u: number): void => {
        vis |= 1 << u;
        for (const v of g[u]) {
            if (((vis >> v) & 1) === 0) {
                dfs(v);
            }
        }
    };

    for (let sub = 1; sub <= m; sub++) {
        let s = 0;
        for (let i = 0; i < n; i++) {
            if ((sub >> i) & 1) {
                s += nums[i];
            }
        }
        if (s % 2 !== 0) {
            continue;
        }
        vis = m ^ sub;
        dfs(sub.toString(2).length - 1);
        if (vis === m) {
            ans++;
        }
    }
    return ans;
}

All Problems

All Solutions