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.

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

• Time: O(N)
• Space: O(N)

public int numberOfConnectedComponents_2(int[][] edges, int n) {
    QuickUnion uf = new QuickUnion(n);
    for (int i = 0; i < edges.length; i++) {
        uf.union(edges[i][0], edges[i][1]);
    }
    return uf.count;
}
// Union Find / Quick-union
class QuickUnion {
    int[] roots;
    int count;
    QuickUnion(int n) {
        count = n;
        roots = new int[n];
        for (int i = 0; i < n; i++) {
            roots[i] = i;
        }
    }
    private Integer find(int p) {
        while (roots[p] != p) {
            p = roots[p];
        }
        return p;
    }
    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot)
            return;
        roots[pRoot] = qRoot;
        count--;
    }
}