Skip to content

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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);
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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;
}

Comments