Connected Components in an Undirected Graph

Medium

The problem

A graph has n nodes numbered 0 to n - 1. Each pair [a, b] in edges is a two-way connection between a and b. A component is a group of nodes that can reach each other. Return the number of components.

Example 1
Input: n = 5, edges = [[0, 1], [1, 2], [3, 4]]
Output: 2
Nodes 0, 1, 2 are one group and nodes 3, 4 are another.
Example 2
Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [3, 4]]
Output: 1
The edges chain all five nodes together.
Example 3
Input: n = 3, edges = []
Output: 3
With no edges, every node is alone.

Limits

1 ≤ n ≤ 2,000
0 ≤ len(edges) ≤ 5,000
There are no repeated edges

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Start with n separate groups. What happens to the count each time an edge joins two different groups?

The idea

Union-find: components = n; every successful union decrements it. (Or DFS and count the starts.)

Target: O(V + E) time

Go function shape

func countComponents(n int, edges [][]int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// CountComponents: number of connected components in an undirected graph of n nodes.
func CountComponents(n int, edges [][]int) int {
	u := NewUF(n)
	for _, e := range edges {
		u.Union(e[0], e[1])
	}
	return u.groups
}

Read the lesson: Graphs: BFS / DFS / Topological Sort