Course4all
Join us on telegram
Home/dsa/Union Find/Number of Connected Components

Number of Connected Components

Master this topic with zero to advance depth.

Number of Connected Components

Given nn nodes and a list of undirected edges, return the number of connected components.

Medium

Examples

Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
Approach 1

Level I: DFS (Graph Traversal)

Intuition

Build an adjacency list. Perform DFS starting from each unvisited node. Each start represents a new component.

⏱ O(V+E)💾 O(V+E)

Detailed Dry Run

Start DFS(0): visits 1, 2. Count=1. Start DFS(3): visits 4. Count=2.

java
class Solution {
    public int countComponents(int n, int[][] edges) {
        List<Integer>[] adj = new ArrayList[n]; for(int i=0; i<n; i++) adj[i]=new ArrayList<>();
        for(int[] e:edges) { adj[e[0]].add(e[1]); adj[e[1]].add(e[0]); }
        boolean[] vis = new boolean[n]; int count = 0;
        for(int i=0; i<n; i++) if(!vis[i]) { count++; dfs(adj, vis, i); }
        return count;
    }
    private void dfs(List<Integer>[] adj, boolean[] vis, int u) {
        vis[u]=true; for(int v:adj[u]) if(!vis[v]) dfs(adj, vis, v);
    }
}
Approach 2

Level III: Union-Find (Direct)

Intuition

Start with nn components. For each edge, perform a union if the nodes are in different components and decrement the count.

⏱ O(V + E \cdot \alpha(V))💾 O(V)

Detailed Dry Run

n=5. [0,1]: Union count=4. [1,2]: Union count=3. [3,4]: Union count=2. Result = 2.

java
class Solution {\n    public int countComponents(int n, int[][] edges) {\n        int[] p = new int[n]; for(int i=0; i<n; i++) p[i]=i;\n        int count = n;\n        for(int[] e:edges) {\n            int r1 = find(p, e[0]), r2 = find(p, e[1]);\n            if(r1 != r2) { p[r1]=r2; count--; }\n        }\n        return count;\n    }\n    private int find(int[] p, int i) { return p[i]==i?i:(p[i]=find(p, p[i])); }\n}
← Previous QuestionRedundant Connection
Next Question →Satisfiability of Equality Equations