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.
public class Solution {
public int countComponents(int n, int[][] edges) {
Map<Integer, Integer> roots = new HashMap<>();
for (int i = 0; i < n; i++) {
roots.put(i, i);
}
int islands = n;
for (int i = 0; i < edges.length; i++) {
int root1 = find(roots, edges[i][0]);
int root2 = find(roots, edges[i][1]);
if (root1 != root2) {
//union root2 into root1
roots.put(root2, root1);
islands--;
}
}
return islands;
}
public int find(Map<Integer, Integer> roots, int id) {
while (roots.get(id) != id) {
//change father to grandfather
roots.put(id, roots.get(roots.get(id))); //path compression
id = roots.get(id);
}
return id;
}
}
