DSA Tutorial
🔍
Connected Components
What Are Connected Components?
A connected component is a maximal subgraph in which every vertex is reachable from every other vertex. A graph can have one component (fully connected) or many components (disconnected).
CONNECTED GRAPH (one component):
0 ─── 1 ─── 3
│ │
2 ─── 4 ─── 5
From any vertex, every other vertex is reachable.
Components: 1 → {0, 1, 2, 3, 4, 5}
DISCONNECTED GRAPH (three components):
0 ─── 1 4 ─── 5
│ │
2 ─── 3 6 7
Component 1: {0, 1, 2, 3}
Component 2: {4, 5, 6}
Component 3: {7} ← isolated vertex
Cannot reach vertex 4 from vertex 0.
Cannot reach vertex 7 from anywhere else.
The Core Insight — Outer Loop
The key to finding all components:
ALGORITHM:
visited = [False] * V
component_id = 0
for each vertex v from 0 to V-1:
if v is NOT visited:
run BFS or DFS from v ← discovers entire component
component_id++ ← increment for next component
WHY IT WORKS:
BFS/DFS from v marks every vertex in v's component as visited.
The outer loop skips already-visited vertices.
Each unvisited vertex starts a NEW component search.
Total components = number of BFS/DFS restarts.
TOTAL TIME: O(V + E)
Each vertex visited exactly ONCE across all BFS/DFS calls.
Each edge examined exactly TWICE (both endpoints) for undirected.
DFS for Connected Components
Based on the reference Java implementation — extended with component labelling and count.
Java
1import java.util.*;
2
3public class ConnectedComponentsDFS {
4
5 // ─────────────────────────────────────────────────
6 // DFS helper — explores one complete component
7 // ─────────────────────────────────────────────────
8 public static void dfs(int start,
9 ArrayList<ArrayList<Integer>> graph,
10 boolean[] visited) {
11 visited[start] = true;
12 System.out.print(start + " ");
13
14 for (int nbh : graph.get(start)) {
15 if (!visited[nbh]) {
16 dfs(nbh, graph, visited);
17 }
18 }
19 }
20
21 // ─────────────────────────────────────────────────
22 // Count and print all components
23 // ─────────────────────────────────────────────────
24 public static int findComponents(ArrayList<ArrayList<Integer>> graph,
25 boolean[] visited, int V) {
26 int count = 0;
27
28 for (int i = 1; i <= V; i++) {
29 if (!visited[i]) {
30 System.out.print("Component " + (count + 1) + ": ");
31 dfs(i, graph, visited);
32 System.out.println();
33 count++;
34 }
35 }
36
37 return count;
38 }
39
40 // ─────────────────────────────────────────────────
41 // Label every vertex with its component ID
42 // ─────────────────────────────────────────────────
43 public static int[] labelComponents(ArrayList<ArrayList<Integer>> graph,
44 int V) {
45 int[] label = new int[V + 1]; // label[v] = component ID of v
46 boolean[] visited = new boolean[V + 1];
47 int compId = 0;
48
49 Arrays.fill(label, -1);
50
51 for (int i = 1; i <= V; i++) {
52 if (!visited[i]) {
53 dfsLabel(i, graph, visited, label, compId);
54 compId++;
55 }
56 }
57
58 return label;
59 }
60
61 private static void dfsLabel(int u,
62 ArrayList<ArrayList<Integer>> graph,
63 boolean[] visited, int[] label, int id) {
64 visited[u] = true;
65 label[u] = id;
66
67 for (int v : graph.get(u)) {
68 if (!visited[v]) {
69 dfsLabel(v, graph, visited, label, id);
70 }
71 }
72 }
73
74 public static void main(String[] args) {
75 Scanner sc = new Scanner(System.in);
76
77 int V = sc.nextInt(); // Number of vertices (1-indexed)
78 int E = sc.nextInt(); // Number of edges
79
80 ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
81 for (int i = 0; i <= V; i++) {
82 graph.add(new ArrayList<>());
83 }
84
85 for (int i = 0; i < E; i++) {
86 int u = sc.nextInt();
87 int v = sc.nextInt();
88 graph.get(u).add(v);
89 graph.get(v).add(u); // Undirected
90 }
91
92 boolean[] visited = new boolean[V + 1];
93
94 System.out.println("=== DFS Component Traversal ===");
95 int total = findComponents(graph, visited, V);
96 System.out.println("Total components: " + total);
97
98 System.out.println("\n=== Component Labels ===");
99 int[] labels = labelComponents(graph, V);
100 for (int i = 1; i <= V; i++) {
101 System.out.println("Vertex " + i + " → Component " + labels[i]);
102 }
103 }
104}
105
106/*
107Sample Input:
1087 4
1091 2
1102 3
1113 4
1125 6
113
114Sample Output:
115=== DFS Component Traversal ===
116Component 1: 1 2 3 4
117Component 2: 5 6
118Component 3: 7
119Total components: 3
120
121=== Component Labels ===
122Vertex 1 → Component 0
123Vertex 2 → Component 0
124Vertex 3 → Component 0
125Vertex 4 → Component 0
126Vertex 5 → Component 1
127Vertex 6 → Component 1
128Vertex 7 → Component 2
129*/Sample Input: 7 4 1 2 2 3 3 4 5 6 Output: === DFS Component Traversal === Component 1: 1 2 3 4 Component 2: 5 6 Component 3: 7 Total components: 3 === Component Labels === Vertex 1 → Component 0 Vertex 2 → Component 0 Vertex 3 → Component 0 Vertex 4 → Component 0 Vertex 5 → Component 1 Vertex 6 → Component 1 Vertex 7 → Component 2
BFS for Connected Components
Same outer-loop structure — just replace the DFS call with a BFS queue.
Java
1import java.util.*;
2
3public class ConnectedComponentsBFS {
4
5 // ─────────────────────────────────────────────────
6 // BFS helper — explores one complete component
7 // ─────────────────────────────────────────────────
8 public static void bfs(int start,
9 ArrayList<ArrayList<Integer>> graph,
10 boolean[] visited) {
11 Queue<Integer> queue = new LinkedList<>();
12 queue.offer(start);
13 visited[start] = true;
14
15 while (!queue.isEmpty()) {
16 int node = queue.poll();
17 System.out.print(node + " ");
18
19 for (int nbh : graph.get(node)) {
20 if (!visited[nbh]) {
21 visited[nbh] = true;
22 queue.offer(nbh);
23 }
24 }
25 }
26 }
27
28 // ─────────────────────────────────────────────────
29 // Count and print all components using BFS
30 // ─────────────────────────────────────────────────
31 public static int findComponents(ArrayList<ArrayList<Integer>> graph,
32 boolean[] visited, int V) {
33 int count = 0;
34
35 for (int i = 1; i <= V; i++) {
36 if (!visited[i]) {
37 System.out.print("Component " + (count + 1) + ": ");
38 bfs(i, graph, visited);
39 System.out.println();
40 count++;
41 }
42 }
43
44 return count;
45 }
46
47 // ─────────────────────────────────────────────────
48 // Label every vertex with its component ID using BFS
49 // ─────────────────────────────────────────────────
50 public static int[] labelComponents(ArrayList<ArrayList<Integer>> graph,
51 int V) {
52 int[] label = new int[V + 1];
53 boolean[] visited = new boolean[V + 1];
54 int compId = 0;
55
56 Arrays.fill(label, -1);
57
58 for (int i = 1; i <= V; i++) {
59 if (!visited[i]) {
60 // BFS from vertex i
61 Queue<Integer> queue = new LinkedList<>();
62 queue.offer(i);
63 visited[i] = true;
64 label[i] = compId;
65
66 while (!queue.isEmpty()) {
67 int u = queue.poll();
68 for (int v : graph.get(u)) {
69 if (!visited[v]) {
70 visited[v] = true;
71 label[v] = compId;
72 queue.offer(v);
73 }
74 }
75 }
76
77 compId++;
78 }
79 }
80
81 return label;
82 }
83
84 public static void main(String[] args) {
85 Scanner sc = new Scanner(System.in);
86
87 int V = sc.nextInt();
88 int E = sc.nextInt();
89
90 ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
91 for (int i = 0; i <= V; i++) {
92 graph.add(new ArrayList<>());
93 }
94
95 for (int i = 0; i < E; i++) {
96 int u = sc.nextInt();
97 int v = sc.nextInt();
98 graph.get(u).add(v);
99 graph.get(v).add(u);
100 }
101
102 boolean[] visited = new boolean[V + 1];
103
104 System.out.println("=== BFS Component Traversal ===");
105 int total = findComponents(graph, visited, V);
106 System.out.println("Total components: " + total);
107
108 System.out.println("\n=== Component Labels (BFS) ===");
109 int[] labels = labelComponents(graph, V);
110 for (int i = 1; i <= V; i++) {
111 System.out.println("Vertex " + i + " → Component " + labels[i]);
112 }
113 }
114}
115
116/*
117Sample Input:
1187 4
1191 2
1202 3
1213 4
1225 6
123
124Sample Output:
125=== BFS Component Traversal ===
126Component 1: 1 2 3 4
127Component 2: 5 6
128Component 3: 7
129Total components: 3
130
131=== Component Labels (BFS) ===
132Vertex 1 → Component 0
133...
134*/Sample Input: 7 4 1 2 2 3 3 4 5 6 Output: === BFS Component Traversal === Component 1: 1 2 3 4 Component 2: 5 6 Component 3: 7 Total components: 3 === Component Labels (BFS) === Vertex 1 → Component 0 Vertex 2 → Component 0 Vertex 3 → Component 0 Vertex 4 → Component 0 Vertex 5 → Component 1 Vertex 6 → Component 1 Vertex 7 → Component 2
DFS vs BFS for Components — Side by Side
SAME GRAPH:
Vertices: 1─7
Edges: 1─2, 2─3, 3─4, 5─6
DFS traversal BFS traversal
──────────────────────────────────────────────────
Component 1: 1 2 3 4 1 2 3 4
Component 2: 5 6 5 6
Component 3: 7 7
Total: 3 3
VISIT ORDER within a component:
DFS: 1 → 2 → 3 → 4 (depth-first — follows one path to the end)
BFS: 1 → 2 → 3 → 4 (same for this linear chain)
For a branching component:
1
/ \
2 3
/ \
4 5
DFS: 1 2 4 5 3 (goes deep: 1→2→4, backtracks, visits 5, backtracks to 1, visits 3)
BFS: 1 2 3 4 5 (level by level: 1, then 2 and 3, then 4 and 5)
WHEN TO PREFER DFS:
✓ Checking if graph is connected (simpler recursive code)
✓ Finding a path between two vertices in same component
✓ Memory-efficient for deep narrow graphs
WHEN TO PREFER BFS:
✓ Finding shortest path within a component
✓ Processing nodes level by level within a component
✓ Better for wide shallow graphs (avoids deep recursion)
✓ No recursion limit issues (iterative by nature)
Dry Run: Component Discovery on Disconnected Graph
Graph: V=7, Edges: 1─2, 2─3, 3─4, 5─6 (7 isolated)
Adjacency list:
1: [2]
2: [1, 3]
3: [2, 4]
4: [3]
5: [6]
6: [5]
7: []
visited = [F, F, F, F, F, F, F, F] (1-indexed, index 0 unused)
components = 0
─── Outer loop: i=1, visited[1]=False ───
BFS from 1:
queue=[1], visited[1]=T
Dequeue 1: print "1 " → enqueue 2
queue=[2], visited[2]=T
Dequeue 2: print "2 " → enqueue 3 (1 already visited)
queue=[3], visited[3]=T
Dequeue 3: print "3 " → enqueue 4 (2 already visited)
queue=[4], visited[4]=T
Dequeue 4: print "4 " → nothing (3 already visited)
queue=[] → Component 1: 1 2 3 4
components = 1
─── Outer loop: i=2, visited[2]=True → SKIP ───
─── Outer loop: i=3, visited[3]=True → SKIP ───
─── Outer loop: i=4, visited[4]=True → SKIP ───
─── Outer loop: i=5, visited[5]=False ───
BFS from 5:
queue=[5], visited[5]=T
Dequeue 5: print "5 " → enqueue 6
queue=[6], visited[6]=T
Dequeue 6: print "6 " → nothing (5 already visited)
queue=[] → Component 2: 5 6
components = 2
─── Outer loop: i=6, visited[6]=True → SKIP ───
─── Outer loop: i=7, visited[7]=False ───
BFS from 7:
queue=[7], visited[7]=T
Dequeue 7: print "7 " → no neighbours
queue=[] → Component 3: 7
components = 3
Final: 3 components ✓
Total time: O(V + E) = O(7 + 4) = O(11)
Union-Find for Dynamic Components
For dynamic graphs (edges added over time), Union-Find tracks components more efficiently than re-running BFS/DFS.
UNION-FIND IDEA:
Each vertex starts in its own component (parent[v] = v).
Adding edge (u,v): merge u's component with v's component.
Query: are u and v in the same component? → find(u) == find(v)
find(u): follow parent pointers to root (with path compression)
union(u,v): connect the two trees by rank
EXAMPLE:
V=6, add edges: (1,2), (2,3), (4,5)
Initial: parent=[_,1,2,3,4,5,6] (each is its own root)
union(1,2): find(1)=1, find(2)=2 → merge → parent[2]=1
union(2,3): find(2)=1, find(3)=3 → merge → parent[3]=1
union(4,5): find(4)=4, find(5)=5 → merge → parent[5]=4
Components:
find(1)=1, find(2)=1, find(3)=1 → same component {1,2,3}
find(4)=4, find(5)=4 → same component {4,5}
find(6)=6 → own component {6}
Count = 3 distinct roots ✓
Java
1public class UnionFind {
2 private int[] parent, rank;
3 private int components;
4
5 public UnionFind(int V) {
6 parent = new int[V + 1];
7 rank = new int[V + 1];
8 components = V;
9 for (int i = 0; i <= V; i++) parent[i] = i; // Each its own root
10 }
11
12 // Find root with PATH COMPRESSION — O(α(V)) ≈ O(1)
13 public int find(int x) {
14 if (parent[x] != x) {
15 parent[x] = find(parent[x]); // Path compression
16 }
17 return parent[x];
18 }
19
20 // Union by RANK — O(α(V)) ≈ O(1)
21 public boolean union(int x, int y) {
22 int px = find(x), py = find(y);
23 if (px == py) return false; // Already same component
24
25 if (rank[px] < rank[py]) { int t = px; px = py; py = t; }
26 parent[py] = px; // Smaller rank merges into larger
27 if (rank[px] == rank[py]) rank[px]++;
28
29 components--;
30 return true;
31 }
32
33 public boolean connected(int x, int y) { return find(x) == find(y); }
34 public int countComponents() { return components; }
35
36 public static void main(String[] args) {
37 java.util.Scanner sc = new java.util.Scanner(System.in);
38 int V = sc.nextInt(), E = sc.nextInt();
39 UnionFind uf = new UnionFind(V);
40
41 for (int i = 0; i < E; i++) {
42 int u = sc.nextInt(), v = sc.nextInt();
43 uf.union(u, v);
44 }
45
46 System.out.println("Total components: " + uf.countComponents());
47
48 // Print which component each vertex belongs to
49 for (int i = 1; i <= V; i++) {
50 System.out.println("Vertex " + i + " → Root " + uf.find(i));
51 }
52 }
53}Output (Union-Find): Total components: 3 Vertex 1 → Root 1 Vertex 2 → Root 1 Vertex 3 → Root 1 Vertex 4 → Root 1 Vertex 5 → Root 5 Vertex 6 → Root 5 Vertex 7 → Root 7
Comparison: DFS vs BFS vs Union-Find
APPROACH SPACE TIME WHEN TO USE
──────────────────────────────────────────────────────────────────
DFS (recursive) O(V + E) O(V + E) Static graph, simple code,
depth-first exploration
DFS (iterative) O(V + E) O(V + E) Static graph, no stack overflow
BFS O(V + E) O(V + E) Static graph, level-order needed,
shortest path within component
Union-Find O(V) O(E × α(V)) Dynamic edges added over time,
≈ O(V) ≈ O(E) online connectivity queries,
Kruskal's MST algorithm
Complexity Summary
| Method | Time | Space | Notes |
|---|---|---|---|
| DFS (recursive) | O(V + E) | O(V) | Call stack depth = longest DFS path |
| DFS (iterative) | O(V + E) | O(V) | Explicit stack avoids recursion limit |
| BFS | O(V + E) | O(V) | Queue size ≤ max level width |
| Union-Find | O(E × α(V)) | O(V) | Near-linear; best for dynamic edges |
All methods visit each vertex once and each edge at most twice — O(V + E) total.
Common Mistakes
Not using an outer loop over all vertices. BFS/DFS from a single vertex only explores one component. For disconnected graphs, the outer loop for i in range(1, V+1): if not visited[i]: bfs/dfs(i) is essential. Without it, isolated components are silently missed.
Marking visited after dequeuing instead of after enqueuing (BFS). In BFS, mark the vertex visited when adding it to the queue — not when processing it. Without this, the same vertex can be enqueued multiple times (from multiple neighbours), causing redundant work and potential incorrect component labelling.
Forgetting isolated vertices in component count. A vertex with no edges forms its own component. The outer loop handles this automatically — if no edges connect to vertex 7, BFS/DFS from vertex 7 discovers only {7} as a component. Ensure the adjacency list has an entry for every vertex, even if that entry is an empty list.
Union-Find: not resetting the component count correctly after multiple test cases. In competitive programming with multiple test cases, reinitialize the parent and rank arrays for each test case. Reusing stale state gives wrong component counts.
0-indexed vs 1-indexed mismatch. The reference implementation uses 1-indexed vertices (loops from 1 to V inclusive, adjacency list size V+1). Mixing 0-indexed and 1-indexed access causes index-out-of-bounds or skips vertex 0 or vertex V. Pick one convention and use it consistently.
Summary
A connected component is a maximal subgraph where every vertex is reachable from every other. Finding all components requires:
The outer loop pattern — iterate over all vertices; when an unvisited vertex is found, start a new BFS or DFS — this discovers one complete component per restart.
Three approaches:
| Approach | Core data structure | Key line |
|---|---|---|
| DFS (recursive) | Call stack | if not visited[nbh]: dfs(nbh) |
| BFS | Queue | queue.append(nbh); visited[nbh]=True |
| Union-Find | Parent/rank arrays | union(u, v) per edge; count() at the end |
All three achieve O(V + E) — each vertex visited once, each edge examined once (twice for undirected).
Choosing between them:
- ›Static graph, want simplicity → DFS recursive
- ›Static graph, avoid stack overflow → BFS or iterative DFS
- ›Edges added dynamically, need online connectivity → Union-Find
In the next topic you will explore Shortest Paths — Dijkstra's algorithm for weighted graphs and Bellman-Ford for negative weights.
Suggested Quiz
A graph with V=6 vertices and no edges has how many connected components?
1/6