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.
We can solve this problem using Union find method.
|
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 30 31 32 |
public int countComponents(int n, int[][] edges) { int count = n; int[] root = new int[n]; // initialize each node is an island for(int i=0; i<n; i++){ root[i]=i; } for(int i=0; i<edges.length; i++){ int x = edges[i][0]; int y = edges[i][1]; int xRoot = getRoot(root, x); int yRoot = getRoot(root, y); if(xRoot!=yRoot){ count--; root[xRoot]=yRoot; } } return count; } public int getRoot(int[] arr, int i){ while(arr[i]!=i){ arr[i]= arr[arr[i]]; i=arr[i]; } return i; } |
Here are some good articles to learn union find data structure:
https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf
http://algs4.cs.princeton.edu/15uf/
