Skip to main content
DevHives

Count Connected Groups

MediumGraphsUnion findDfs153 tests

You are given n nodes numbered 0 to n - 1 and a list edges. Each edge [u, v] joins nodes u and v. The edges have no direction.

A connected group is a set of nodes where you can get from any node in the set to any other node in the set by following edges, and no edge leads out of the set.

Return the number of connected groups in the graph.

Note

  • A node with no edges is a group on its own.
  • No edge appears twice, and no edge joins a node to itself.

Hint: start with n groups, one node in each. For every edge that joins two different groups, merge them with a union-find structure and subtract one. A depth-first search from each unvisited node also works.

Examples

Example 1

Input:
7, [[0,4],[4,5],[1,6],[2,6]]
Output:
3

Nodes 0, 4 and 5 form one group. Nodes 1, 2 and 6 form a second group. Node 3 has no edges, so it is a third group.

Example 2

Input:
4, [[3,2],[2,1],[1,0],[0,3]]
Output:
1

The four edges go around all four nodes, so every node can reach every other node. That is one group.

Example 3

Input:
3, []
Output:
3

There are no edges, so each of the 3 nodes is a group on its own.

Constraints

  • 1 <= n <= 20
  • 0 <= edges.length <= 30
  • edges[i] = [u, v] with 0 <= u, v < n and u != v
  • No edge appears twice ([u, v] and [v, u] count as the same edge).

Run checks your code against the 3 examples. Submit checks it against all 153 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.