LC-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.

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;
    }
}