323. Number of Connected Components in an Undirected Graph

Published on April 23, 2023

Question

You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.

Return the number of connected components in the graph.

Algorithm

Typical question we could utilize union find.

At first, we let count = n, where all the nodes represent a tree(component), and then by doing union we could put connected nodes into same group(tree) and count minus one. Finally when all the nodes are union, the count number is the component number, in other words, the disconnected set(tree) number.

Code

class Solution {
    int[] parents;
    int count;
    
    public int countComponents(int n, int[][] edges) {
        parents = new int[n];
        count = n;
        for (int i = 0; i < n; i++) {
            parents[i] = i;
        }
        
        for (int[] edge : edges) {
            union(edge[0], edge[1]);
        }
        
        return count;
    }
    
    private int find(int x) {
        if (x != parents[x]) {
            parents[x] = find(parents[x]);
        }
        return parents[x];
    }
    
    private void union(int x, int y) {
        int xRoot = find(x);
        int yRoot = find(y);
        if (xRoot == yRoot) {
            return;
        }
        parents[yRoot] = xRoot;
        count--;
    }
}