[LeetCode] 323. Number of Connected Components in an Undirected Graph

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Example 1:

     0          3
     |          |
     1 --- 2    4

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.

Example 2:

     0           4
     |           |
     1 --- 2 --- 3

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1.

Note:
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Thought process:

This question is a good practice on union-find.

The idea is to think of each connected component as a tree. As we iterate through the edges, we set one of the node as the parent node of the other and decrement n. This process is called union, which essentially adds the nodes into the tree they belong to. Before we can union two nodes, we need to check if they are already on the same tree, in order not to decrement n by mistake. This can be done by comparing the two root nodes of the trees the nodes belong to. This process is the find part.

Solution:

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

public class Solution { public int countComponents(int n, int[][] edges) { int[] roots = new int[n]; for (int i = 0; i < n; i++) { roots[i] = i; } for (int i = 0; i < edges.length; i++) { int r1 = find(roots, edges[i][0]); int r2 = find(roots, edges[i][1]); if (r1 != r2) { roots[r1] = r2; n--; } } return n; } private int find(int[] roots, int key) { while (roots[key] != key) { key = roots[key]; } return key; } }

Time complexity:

Say there are v nodes and e edges. Union takes O(e) loops where each loop may take O(v) time. So the overall time complexity is O(ve).