Back to DSA

Number of Connected Components in an Undirected Graph

easy
Acceptance: 60%
GraphsUnion FindDFS

Given n nodes (labeled 0 to n-1) and a set of undirected edges, count how many separate connected components exist in the graph.

Examples

Example 1:
Input:n = 6, edges = [[0,1],[2,3],[4,5]]
Output:3
Explanation: Three pairs of connected nodes form three separate components.
Example 2:
Input:n = 4, edges = [[0,1],[1,2],[2,3]]
Output:1
Explanation: All four nodes are linked in a single chain.

Hints

Related Problems

Clone GraphmediumPacific Atlantic Water FlowmediumRotting OrangesmediumWalls and GatesmediumShortest Path in Binary Matrixmedium
00:00
class Solution {
    public int countComponents(int n, int[][] edges) {
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        int components = n;
        for (int[] e : edges) {
            int px = find(parent, e[0]), py = find(parent, e[1]);
            if (px != py) { parent[px] = py; components--; }
        }
        return components;
    }

    private int find(int[] parent, int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
}
Time complexityO(E * alpha(V))
Space complexityO(V)