Tap here to switch tabs
Problem
Submissions

Problem: Count Connected Subgraphs with Even Node Sum

Count Connected Subgraphs with Even Node Sum asks you to count nonempty connected node subsets in an undirected graph whose assigned zero-or-one values add up to an even total.

Statement

You are given an undirected graph with nn nodes labeled from 00 to n−1n - 1, represented by an integer array nums of length nn and a 2D2 {D} integer array edges where edges[i] =[ui,vi]= [u_i, v_i] represents an edge connecting node uiu_i and node viv_i. Each node ii has an assigned value nums[i].

A subset of nodes forms a connected subgraph if it is nonempty and every pair of nodes in the subset is connected by a path using only nodes and edges within the subset.

Return the total number of nonempty connected subgraphs where the sum of the node values is even.

Constraints:

  • 1≤n=1 \le n = nums.length ≤13\le 13

  • nums[i] is 00 or 11.

  • 0≤0 \le edges.length ≤n×(n−1)2\le \frac{n \times (n - 1)}{2}

  • edges[i] =[ui,vi]= [u_i, v_i]

  • 0≤ui<vi<n0 \le u_i < v_i < n

  • All edges are distinct.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Count Connected Subgraphs with Even Node Sum

Count Connected Subgraphs with Even Node Sum asks you to count nonempty connected node subsets in an undirected graph whose assigned zero-or-one values add up to an even total.

Statement

You are given an undirected graph with nn nodes labeled from 00 to n−1n - 1, represented by an integer array nums of length nn and a 2D2 {D} integer array edges where edges[i] =[ui,vi]= [u_i, v_i] represents an edge connecting node uiu_i and node viv_i. Each node ii has an assigned value nums[i].

A subset of nodes forms a connected subgraph if it is nonempty and every pair of nodes in the subset is connected by a path using only nodes and edges within the subset.

Return the total number of nonempty connected subgraphs where the sum of the node values is even.

Constraints:

  • 1≤n=1 \le n = nums.length ≤13\le 13

  • nums[i] is 00 or 11.

  • 0≤0 \le edges.length ≤n×(n−1)2\le \frac{n \times (n - 1)}{2}

  • edges[i] =[ui,vi]= [u_i, v_i]

  • 0≤ui<vi<n0 \le u_i < v_i < n

  • All edges are distinct.