Number of Connected Components In An Undirected Graph

MediumGraphDFSBFSUnion FindConnected Components
Category: Graphs
Companies that ask this question:
GoogleAmazonFacebookMicrosoftLinkedIn

Approach

Number of Connected Components In An Undirected Graph

Problem Statement

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

Return the number of connected components in the graph.

A connected component is a maximal set of nodes where every node is reachable from every other node in the set.

Example

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

Output: 2

Explanation:

  • Component 1: 2 (nodes 0, 1, and 2 are connected)
  • Component 2: 4 (nodes 3 and 4 are connected)
  • Node 2 is isolated (forms its own component if it had no edges, but here it connects to 1)

Approach 1: Depth-First Search (DFS)

Algorithm

  1. Build Adjacency List: Convert the edge list into an adjacency list representation for efficient neighbor lookup
  2. Initialize Tracking: Create a visited set to track which nodes have been explored
  3. Scan All Nodes: Iterate through each node from 0 to n-1
  4. Start New Component: When finding an unvisited node:
    • Increment component counter
    • Start DFS from that node
  5. DFS Exploration:
    • Mark current node as visited
    • Recursively explore all unvisited neighbors
    • All nodes reached belong to the same component
  6. Return Count: After scanning all nodes, return the total component count

Time Complexity

  • O(V + E) where V is the number of vertices (nodes) and E is the number of edges
  • Each node is visited once
  • Each edge is traversed at most twice (once from each endpoint)

Space Complexity

  • O(V + E) for the adjacency list
  • O(V) for the visited set and recursion stack

Approach 2: Union-Find (Disjoint Set Union)

Algorithm

  1. Initialize Union-Find: Create a parent array where each node is its own parent initially
  2. Process Edges: For each edge [u, v]:
    • Find the root of u
    • Find the root of v
    • If they have different roots, union them (connect the components)
  3. Count Components: Count how many nodes are their own parent (root nodes)

Time Complexity

  • O(E * α(V)) where α is the inverse Ackermann function (nearly constant)
  • With path compression and union by rank, operations are nearly O(1)

Space Complexity

  • O(V) for the parent and rank arrays

Key Insights

  1. Connected Components: A connected component is a maximal subgraph where every pair of nodes has a path between them

  2. DFS vs Union-Find:

    • DFS: More intuitive, easier to implement, good for exploring graph structure
    • Union-Find: More efficient for dynamic connectivity, online algorithms

  3. Graph Representation: Adjacency list is preferred over adjacency matrix for sparse graphs

  4. Visit Tracking: Essential to avoid revisiting nodes and infinite loops

Common Patterns

  • Graph Traversal: DFS/BFS to explore connected regions
  • Union-Find: For dynamic connectivity and disjoint set operations
  • Component Counting: Count new DFS starts or root nodes

Related Problems

  • Number of Islands (2D grid version)
  • Friend Circles / Number of Provinces
  • Graph Valid Tree
  • Redundant Connection

Solution

java
1class Solution {
2    // Approach 1: DFS Solution
3    public int countComponents(int n, int[][] edges) {
4        // Build adjacency list
5        List<List<Integer>> graph = new ArrayList<>();
6        for (int i = 0; i < n; i++) {
7            graph.add(new ArrayList<>());
8        }
9
10        for (int[] edge : edges) {
11            graph.get(edge[0]).add(edge[1]);
12            graph.get(edge[1]).add(edge[0]);
13        }
14
15        boolean[] visited = new boolean[n];
16        int count = 0;
17
18        // Scan all nodes
19        for (int i = 0; i < n; i++) {
20            if (!visited[i]) {
21                count++;
22                dfs(i, graph, visited);
23            }
24        }
25
26        return count;
27    }
28
29    private void dfs(int node, List<List<Integer>> graph, boolean[] visited) {
30        visited[node] = true;
31
32        for (int neighbor : graph.get(node)) {
33            if (!visited[neighbor]) {
34                dfs(neighbor, graph, visited);
35            }
36        }
37    }
38
39    // Approach 2: Union-Find Solution
40    public int countComponentsUnionFind(int n, int[][] edges) {
41        int[] parent = new int[n];
42        int[] rank = new int[n];
43
44        // Initialize: each node is its own parent
45        for (int i = 0; i < n; i++) {
46            parent[i] = i;
47            rank[i] = 0;
48        }
49
50        int components = n;
51
52        // Process each edge
53        for (int[] edge : edges) {
54            if (union(edge[0], edge[1], parent, rank)) {
55                components--;
56            }
57        }
58
59        return components;
60    }
61
62    private int find(int x, int[] parent) {
63        if (parent[x] != x) {
64            parent[x] = find(parent[x], parent); // Path compression
65        }
66        return parent[x];
67    }
68
69    private boolean union(int x, int y, int[] parent, int[] rank) {
70        int rootX = find(x, parent);
71        int rootY = find(y, parent);
72
73        if (rootX == rootY) {
74            return false; // Already in same component
75        }
76
77        // Union by rank
78        if (rank[rootX] > rank[rootY]) {
79            parent[rootY] = rootX;
80        } else if (rank[rootX] < rank[rootY]) {
81            parent[rootX] = rootY;
82        } else {
83            parent[rootY] = rootX;
84            rank[rootX]++;
85        }
86
87        return true;
88    }
89
90    // Approach 3: BFS Solution
91    public int countComponentsBFS(int n, int[][] edges) {
92        // Build adjacency list
93        List<List<Integer>> graph = new ArrayList<>();
94        for (int i = 0; i < n; i++) {
95            graph.add(new ArrayList<>());
96        }
97
98        for (int[] edge : edges) {
99            graph.get(edge[0]).add(edge[1]);
100            graph.get(edge[1]).add(edge[0]);
101        }
102
103        boolean[] visited = new boolean[n];
104        int count = 0;
105
106        for (int i = 0; i < n; i++) {
107            if (!visited[i]) {
108                count++;
109                bfs(i, graph, visited);
110            }
111        }
112
113        return count;
114    }
115
116    private void bfs(int start, List<List<Integer>> graph, boolean[] visited) {
117        Queue<Integer> queue = new LinkedList<>();
118        queue.offer(start);
119        visited[start] = true;
120
121        while (!queue.isEmpty()) {
122            int node = queue.poll();
123
124            for (int neighbor : graph.get(node)) {
125                if (!visited[neighbor]) {
126                    visited[neighbor] = true;
127                    queue.offer(neighbor);
128                }
129            }
130        }
131    }
132}
133
Loading visualizer...