Connected Components in an Undirected Graph
Problem link: https://www.geeksforgeeks.org/problems/connected-components-in-an-undirected-graph/1
Problem Statement
Given an undirected graph with V vertices numbered from 0 to V-1 and E edges, represented as a 2D array edges[][], where each entry edges[i] = [u, v] denotes an edge between vertices u and v.
Return a list of all connected components. Each connected component should be represented as a list of its vertices.
Input
Integer V (number of vertices) 2D array edges[][] where edges[i] = [u, v] representing undirected edges
Output
Return a list of lists, where each inner list represents a connected component containing its vertices.
Example
Input: V = 5 edges = [[0,1],[2,1],[3,4]]
Output: [[0,1,2],[3,4]]
Explanation
Start DFS from node 0 → reach 1 → reach 2 → first component = [0,1,2] Next unvisited node = 3 → reach 4 → second component = [3,4]
Brute Force
Intuition
Try to group nodes by checking reachability manually between nodes. This leads to redundant traversals and inefficient grouping.
Approach
- Build adjacency list
- For each node, check reachable nodes using DFS
- Store reachable nodes as a component
- Mark visited nodes to avoid repetition
Dry Run
Start from 0 → collect [0,1,2] Then from 3 → collect [3,4]
Visualization
Code (Java)
import java.util.*;
public class Solution {
void dfs(int node, boolean[] visited, ArrayList<ArrayList<Integer>> adj, ArrayList<Integer> comp) {
visited[node] = true;
comp.add(node);
for (int nei : adj.get(node)) {
if (!visited[nei]) dfs(nei, visited, adj, comp);
}
}
public ArrayList<ArrayList<Integer>> connectedcomponents(int V, int[][] edges) {
ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
boolean[] visited = new boolean[V];
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
for (int i = 0; i < V; i++) {
if (!visited[i]) {
ArrayList<Integer> comp = new ArrayList<>();
dfs(i, visited, adj, comp);
res.add(comp);
}
}
return res;
}
}
Complexity Analysis
DFS visits every node once and processes each edge twice in undirected graph. Storing components requires O(V) space.
Optimal Solution
Intuition
This problem is inherently optimal with DFS/BFS. The only improvement is clean traversal and avoiding redundant work.
Approach
- Build adjacency list
- Maintain visited array
- For each unvisited node, run DFS
- Collect nodes into component list
- Add component to result
Dry Run
i=0 → DFS → [0,1,2] i=3 → DFS → [3,4]
Code (Java)
/* Same as above */
Complexity Analysis
Optimal traversal since every node and edge is processed once.
Quick Revision (Brute Force)
- Build adjacency list
- Run DFS from each unvisited node
- Store nodes in component list
Quick Revision (Optimal)
- DFS/BFS traversal
- Each DFS gives one component
- Time complexity O(V+E)