1class Solution {
2    // Bitmask tracking visited nodes during the connectivity DFS
3    private int visited;
4    // Full bitmask representing all n nodes (n bits set to 1)
5    private int fullMask;
6    // Adjacency list of the graph
7    private List<Integer>[] graph;
8
9    /**
10     * Counts the number of connected subgraphs (non-empty node subsets that form
11     * a single connected component) whose total node-value sum is even.
12     */
13    public int evenSumSubgraphs(int[] nums, int[][] edges) {
14        int n = nums.length;
15
16        // Build the undirected adjacency list
17        graph = new List[n];
18        Arrays.setAll(graph, k -> new ArrayList<>());
19        for (int[] edge : edges) {
20            graph[edge[0]].add(edge[1]);
21            graph[edge[1]].add(edge[0]);
22        }
23
24        // fullMask has the lowest n bits set, representing every node
25        fullMask = (1 << n) - 1;
26
27        int ans = 0;
28        // Enumerate every non-empty subset of nodes as a bitmask
29        for (int subset = 1; subset <= fullMask; subset++) {
30            // Compute the sum of node values included in this subset
31            int sum = 0;
32            for (int i = 0; i < n; i++) {
33                if (((subset >> i) & 1) == 1) {
34                    sum += nums[i];
35                }
36            }
37
38            // Skip subsets whose sum is odd
39            if (sum % 2 != 0) {
40                continue;
41            }
42
43            // Mark all nodes NOT in the subset as already visited, so the DFS
44            // is confined to nodes within the current subset
45            visited = fullMask ^ subset;
46
47            // Start the DFS from the lowest-index node present in the subset
48            dfs(Integer.numberOfTrailingZeros(subset));
49
50            // If every node is now marked visited, the subset is fully connected
51            if (visited == fullMask) {
52                ans++;
53            }
54        }
55        return ans;
56    }
57
58    /**
59     * Depth-first search that marks node u and all reachable unvisited
60     * neighbours (limited to the current subset) as visited.
61     */
62    private void dfs(int u) {
63        // Mark the current node as visited
64        visited |= 1 << u;
65        // Visit every adjacent node that has not been visited yet
66        for (int v : graph[u]) {
67            if (((visited >> v) & 1) == 0) {
68                dfs(v);
69            }
70        }
71    }
72}
73

1class Solution {
2public:
3    int evenSumSubgraphs(vector<int>& nums, vector<vector<int>>& edges) {
4        int n = nums.size();
5
6        // Build the adjacency list representation of the graph
7        vector<vector<int>> graph(n);
8        for (auto& edge : edges) {
9            graph[edge[0]].push_back(edge[1]);
10            graph[edge[1]].push_back(edge[0]);
11        }
12
13        // fullMask represents the bitmask where all n nodes are set
14        int fullMask = (1 << n) - 1;
15        int answer = 0;
16
17        // visited is a bitmask tracking which nodes have been reached during DFS
18        int visited;
19
20        // DFS marks every node reachable from u (within the current subset).
21        // Nodes outside the subset are pre-marked as visited so we never enter them.
22        auto dfs = [&](this auto dfs, int u) -> void {
23            visited |= 1 << u; // Mark the current node as visited
24            for (int next : graph[u]) {
25                // Only traverse into nodes that have not been visited yet
26                if (((visited >> next) & 1) == 0) {
27                    dfs(next);
28                }
29            }
30        };
31
32        // Enumerate every non-empty subset of nodes
33        for (int subset = 1; subset <= fullMask; subset++) {
34            // Compute the sum of node values contained in this subset
35            int sum = 0;
36            for (int i = 0; i < n; i++) {
37                if ((subset >> i) & 1) {
38                    sum += nums[i];
39                }
40            }
41
42            // Skip subsets whose total sum is odd
43            if (sum % 2 != 0) {
44                continue;
45            }
46
47            // Pre-mark all nodes NOT in the subset as visited,
48            // so the DFS stays strictly inside the subset.
49            visited = fullMask ^ subset;
50
51            // Start DFS from the highest-index node present in the subset.
52            // 31 - __builtin_clz(subset) gives the position of the most
53            // significant set bit, i.e. one valid starting node.
54            dfs(31 - __builtin_clz(subset));
55
56            // If after the DFS every node is visited, then all nodes inside
57            // the subset were reachable from the start => the subset is connected.
58            if (visited == fullMask) {
59                answer++;
60            }
61        }
62
63        return answer;
64    }
65};
66

1/**
2 * Counts the number of non-empty connected subgraphs (vertex subsets that are
3 * connected in the induced subgraph) whose total node-value sum is even.
4 *
5 * @param nums  - Value assigned to each node, indexed 0..n-1.
6 * @param edges - Undirected edges as [u, v] pairs.
7 * @returns The count of valid connected subsets with an even value sum.
8 */
9function evenSumSubgraphs(nums: number[], edges: number[][]): number {
10    const n: number = nums.length;
11
12    // Build adjacency list for the undirected graph.
13    const graph: number[][] = Array.from({ length: n }, () => []);
14    for (const [u, v] of edges) {
15        graph[u].push(v);
16        graph[v].push(u);
17    }
18
19    // Full bitmask representing all n nodes being present/visited.
20    const fullMask: number = (1 << n) - 1;
21
22    let answer: number = 0;
23    let visited: number = 0; // Bitmask of visited nodes during a DFS run.
24
25    /**
26     * Depth-first search starting from node `start`.
27     * Only traverses nodes that are part of the current subset, because nodes
28     * outside the subset are pre-marked as visited before the call.
29     *
30     * @param start - The node index to begin traversal from.
31     */
32    const dfs = (start: number): void => {
33        visited |= 1 << start; // Mark current node as visited.
34        for (const next of graph[start]) {
35            // Visit each unvisited neighbor (neighbors outside the subset are
36            // already marked, so they are skipped automatically).
37            if (((visited >> next) & 1) === 0) {
38                dfs(next);
39            }
40        }
41    };
42
43    // Enumerate every non-empty subset of the n nodes.
44    for (let subset = 1; subset <= fullMask; subset++) {
45        // Compute the sum of node values contained in this subset.
46        let sum: number = 0;
47        for (let i = 0; i < n; i++) {
48            if ((subset >> i) & 1) {
49                sum += nums[i];
50            }
51        }
52
53        // Skip subsets whose total value sum is odd.
54        if (sum % 2 !== 0) {
55            continue;
56        }
57
58        // Pre-mark all nodes NOT in the subset as visited, so the DFS is
59        // confined to the induced subgraph of `subset`.
60        visited = fullMask ^ subset;
61
62        // Pick the lowest set bit of `subset` as the DFS starting node.
63        const startNode: number = subset & -subset;
64        dfs(Math.log2(startNode));
65
66        // If every node became visited, the subset's induced subgraph is
67        // connected (all subset nodes were reachable from the start node).
68        if (visited === fullMask) {
69            answer++;
70        }
71    }
72
73    return answer;
74}
75