15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
A connected component of an undirected graph is a maximal set of vertices that can all reach one another. To count them, scan the vertices in order and start a DFS from every unvisited one, giving each reached vertex the same id. The number of DFS starts is the component count, found in O(V + E) time.
| Component | Maximal set of mutually reachable vertices |
|---|---|
| Count | One per DFS started from an unvisited vertex |
| Time | O(V + E) |
| Auxiliary space | O(V): visited, componentId and the recursion stack |
| Same-component test | componentId[u] = componentId[v], no new traversal |
| Example | A-B-C, D-E and F alone give 3 components |
Assume you can:
visited array or set during DFS,In an undirected graph, a connected component is a maximal set of vertices that can all reach one another.
“Maximal” means that every vertex reachable from the group belongs to that group. Reachable vertices cannot be split into separate components.
Label every vertex with a component identifier:
For the same-component query, once identifiers are assigned:
1sameComponent(u, v) is true exactly when componentId[u] = componentId[v].The adjacency list represents an undirected graph. If A lists B, then B lists A.
Sources used for reachability and traversal scope:
Use these ordered vertices:
1[A, B, C, D, E, F]Their adjacency lists are:
1A: [B]
2B: [A, C]
3C: [B]
4D: [E]
5E: [D]
6F: []Draw the graph as three separated groups:
1A -- B -- C D -- E FThere is a path from A to B and C, so they form one reachable group.
There is a path between D and E, so they form another group.
F has no edges. It is still a vertex, so it is a component containing only itself.
The identifiers are:
1A: 1, B: 1, C: 1, D: 2, E: 2, F: 3The final component count is:
1componentCount = 3Keep three pieces of state:
1visited which vertices have already been reached
2componentId the identifier assigned to each vertex
3componentCount how many component traversals have startedScanning A to F: A starts component 1 and reaches B, C; B and C are skipped; D starts component 2 and reaches E; F starts component 3 alone. componentCount ends at 3.
Before scanning any vertex:
1visited = {}
2componentId = unset for A, B, C, D, E, F
3componentCount = 0Now scan vertices in their given order.
| State | Outer-scan position | Action | visited | Assigned identifiers | componentCount |
|---|---|---|---|---|---|
| 0 | Begin at A | Nothing has been visited yet. | {} | all unset | 0 |
| 1 | A | A is unvisited. Increase count to 1. DFS from A reaches A, B, and C, assigning id 1 to each. | {A, B, C} | A:1, B:1, C:1 | 1 |
| 2 | B, then C | Both are already visited. Start no DFS. | {A, B, C} | unchanged | 1 |
| 3 | D | D is unvisited. Increase count to 2. DFS from D reaches D and E, assigning id 2 to each. | {A, B, C, D, E} | A:1, B:1, C:1, D:2, E:2 | 2 |
| 4 | E, then F | E is visited, so skip it. F is unvisited. Increase count to 3. DFS from F assigns id 3 to F. | {A, B, C, D, E, F} | A:1, B:1, C:1, D:2, E:2, F:3 | 3 |
| 5 | Scan finished | Every vertex has an identifier. | {A, B, C, D, E, F} | A:1, B:1, C:1, D:2, E:2, F:3 | 3 |
At each scan vertex, make this decision:
1Is this vertex already visited?
2
3Yes -> skip it.
4No -> this begins one new component traversal.After scanning through some vertex position, examine every vertex already marked visited.
Each visited vertex has exactly one component identifier. Its identifier came from the DFS traversal that reached it.
No later traversal starts from a vertex already marked visited.
The invariant is:
After the outer scan has processed vertices through index
i, every visited vertex belongs to exactly one assigned component, and that component is exactly the set reached by the DFS that assigned its identifier. No later traversal starts from a visited vertex.
In the example:
A, A, B, and C are all visited and have id 1.B and C, it does not start new DFS calls from them.D, D and E have id 2.F is still unvisited until the scan reaches it, so it receives its own id 3.The visited structure must be global for the entire outer scan. Resetting it before each DFS would let later scans treat old vertices as new components.
Start with every vertex unvisited and every identifier unset.
Process every vertex in order.
For each scan vertex v:
v is already visited, do nothing.v has not been reached by any earlier traversal.componentCount.v.DFS checks reachability and fills in componentId.
For example, when the scan finds unvisited D:
1componentCount becomes 2
2DFS(D, 2) marks D with id 2
3DFS follows D -> E
4DFS(E, 2) marks E with id 2After preprocessing, answer a same-component query without another traversal:
1componentId[u] = componentId[v]For the example:
1sameComponent(A, C) -> 1 = 1 -> true
2sameComponent(B, E) -> 1 = 2 -> false
3sameComponent(F, F) -> 3 = 3 -> trueInput contract
adjacencyList represents an undirected graph.adjacencyList.vertices is the ordered list of vertices.adjacencyList.neighbors(v) returns the vertices adjacent to v.adjacencyList.vertices.Return value
componentCount.componentId, mapping every input vertex to an integer identifier from 1 through componentCount.Mutation behavior
adjacencyList.visited and componentId structures.Helper contract
markComponent(v, id, adjacencyList, visited, componentId) is called only when v is unvisited.v that have not already been visited, assigning each id.101 function connectedComponents(adjacencyList):
202 vertices <- adjacencyList.vertices
303 visited <- map with false for every vertex in vertices
404 componentId <- map with unset for every vertex in vertices
505 componentCount <- 0
606
707 for each vertex v in vertices:
808 if visited[v] = false:
909 componentCount <- componentCount + 1
1010 markComponent(v, componentCount, adjacencyList, visited, componentId)
1111
1212 return (componentCount, componentId)113 function markComponent(v, id, adjacencyList, visited, componentId):
214 visited[v] <- true
315 componentId[v] <- id
416
517 for each neighbor w in adjacencyList.neighbors(v):
618 if visited[w] = false:
719 markComponent(w, id, adjacencyList, visited, componentId)The boundary is at line 18. DFS recurses only to an unvisited neighbor. A self-loop or duplicate edge may cause an extra adjacency inspection, but it cannot cause another component assignment after the vertex is visited.
Use the same graph:
1A: [B]
2B: [A, C]
3C: [B]
4D: [E]
5E: [D]
6F: []| Pseudocode line | State change |
|---|---|
| 02 | vertices = [A, B, C, D, E, F] |
| 03 | visited = {A:false, B:false, C:false, D:false, E:false, F:false} |
| 04 | componentId = {A:unset, B:unset, C:unset, D:unset, E:unset, F:unset} |
| 05 | componentCount = 0 |
A| Pseudocode line | State change |
|---|---|
| 07 | The outer loop selects v = A. |
| 08 | visited[A] is false. Enter the if. |
| 09 | componentCount changes from 0 to 1. |
| 10 | Call markComponent(A, 1, ...). |
| 14 | visited[A] changes to true. |
| 15 | componentId[A] changes from unset to 1. |
| 17 | Inspect neighbor B of A. |
| 18 | visited[B] is false. |
| 19 | Call markComponent(B, 1, ...). |
| 14 | visited[B] changes to true. |
| 15 | componentId[B] changes from unset to 1. |
| 17 | Inspect neighbor A of B. |
| 18 | visited[A] is true. Do not recurse. |
| 17 | Inspect next neighbor C of B. |
| 18 | visited[C] is false. |
| 19 | Call markComponent(C, 1, ...). |
| 14 | visited[C] changes to true. |
| 15 | componentId[C] changes from unset to 1. |
| 17 | Inspect neighbor B of C. |
| 18 | visited[B] is true. Do not recurse. |
| 13–19 | markComponent(C, 1, ...) returns, then markComponent(B, 1, ...) returns, then markComponent(A, 1, ...) returns. |
State now:
1visited = {A, B, C}
2componentId = {A:1, B:1, C:1, D:unset, E:unset, F:unset}
3componentCount = 1B and C| Pseudocode line | State change |
|---|---|
| 07 | Select v = B. |
| 08 | visited[B] is true. Skip lines 09 and 10. |
| 07 | Select v = C. |
| 08 | visited[C] is true. Skip lines 09 and 10. |
No state changes occur.
D| Pseudocode line | State change |
|---|---|
| 07 | Select v = D. |
| 08 | visited[D] is false. Enter the if. |
| 09 | componentCount changes from 1 to 2. |
| 10 | Call markComponent(D, 2, ...). |
| 14 | visited[D] changes to true. |
| 15 | componentId[D] changes from unset to 2. |
| 17 | Inspect neighbor E of D. |
| 18 | visited[E] is false. |
| 19 | Call markComponent(E, 2, ...). |
| 14 | visited[E] changes to true. |
| 15 | componentId[E] changes from unset to 2. |
| 17 | Inspect neighbor D of E. |
| 18 | visited[D] is true. Do not recurse. |
| 13–19 | markComponent(E, 2, ...) returns, then markComponent(D, 2, ...) returns. |
State now:
1visited = {A, B, C, D, E}
2componentId = {A:1, B:1, C:1, D:2, E:2, F:unset}
3componentCount = 2E and F| Pseudocode line | State change |
|---|---|
| 07 | Select v = E. |
| 08 | visited[E] is true. Skip lines 09 and 10. |
| 07 | Select v = F. |
| 08 | visited[F] is false. Enter the if. |
| 09 | componentCount changes from 2 to 3. |
| 10 | Call markComponent(F, 3, ...). |
| 14 | visited[F] changes to true. |
| 15 | componentId[F] changes from unset to 3. |
| 17 | F has no neighbors, so the neighbor loop performs no iterations. |
| 13–19 | markComponent(F, 3, ...) returns. |
| 12 | Return (3, {A:1, B:1, C:1, D:2, E:2, F:3}). |
Correctness requires two claims:
componentCount equals the number of connected components.Consider a call:
1markComponent(v, id, ...)The helper immediately marks v visited and assigns componentId[v] = id.
For every neighbor w of v:
w is already visited, the helper does not recurse again;w is unvisited, the helper recursively marks w with the same id.Every recursive call follows an actual graph edge. Every vertex receiving id is reachable from the traversal start.
DFS examines the neighbors of every reached vertex. If some vertex is reachable from the start, there is a path to it. DFS follows that path one unvisited vertex at a time until it reaches that vertex. The helper assigns id to every vertex reachable from its start.
One helper call marks exactly one connected component.
Before line 07 runs:
componentCount is 0.No component has been claimed incorrectly. The outer-loop invariant holds before the scan begins.
Suppose the invariant holds before processing a scan vertex v.
If v is already visited, lines 09 and 10 do not run. No existing identifier changes, and no new traversal begins from a visited vertex. The invariant remains true.
If v is unvisited, no earlier traversal reached v. The algorithm increments componentCount once and calls DFS from v. As shown above, that DFS assigns the new identifier to exactly the vertices reachable from v. Those vertices form one connected component. Earlier visited vertices keep their existing identifiers, and this traversal cannot merge with them. If it could reach an earlier visited vertex, then v would have been reachable from that earlier traversal and would already be visited.
After processing v, every visited vertex still belongs to exactly one correctly assigned component, and later traversals will not start from a visited vertex. The invariant is preserved.
The outer loop scans every vertex exactly once.
When it finishes, every vertex has been considered:
Every vertex has exactly one component identifier.
A new count is added exactly once for each DFS started from an unvisited vertex. Each such DFS marks exactly one connected component, and no component can start another DFS later because all of its vertices are visited. componentCount is exactly the number of connected components.
Let:
V be the number of vertices,E be the number of adjacency entries considered by the graph representation.The outer scan at line 07 checks every vertex:
1V checks -> O(V)DFS may start more than once, but visited is shared across all calls. Once a vertex is visited, it never starts another DFS traversal.
Every vertex is processed by the DFS helper at most once.
When DFS processes a vertex, it inspects that vertex’s adjacency entries at line 17. Across all DFS calls, the total adjacency work is:
1O(E)Combining the outer scan and adjacency inspection:
1O(V) + O(E) = O(V + E)For the worked example:
A, B, C, D, E, and F: 6 vertex checks;A: 1,B: 2,C: 1,D: 1,E: 1,F: 0.The algorithm’s total time is therefore O(V + E).
Auxiliary space, excluding the graph itself:
visited: O(V),componentId: O(V),O(V).Auxiliary space is:
1O(V)Incorrect assumption:
1Start DFS from the first vertex and return count = 1.Small exposing input:
1A: [B]
2B: [A]
3C: [D]
4D: [C]Starting from A visits only:
1{A, B}Wrong result:
1componentCount = 1But C and D are disconnected from A and B.
Correction:
1Use an outer loop over every vertex.
2When the scan reaches unvisited C, start another DFS.visited before each DFSIncorrect line:
1visited <- all falseplaced inside the outer loop before each DFS.
Exposing input:
1A: [B]
2B: [A, C]
3C: [B]After DFS from A, all three vertices should remain marked visited. Resetting visited before later checks can make scanning B or C treat them as new traversal starts.
Wrong result:
1potentially componentCount = 3Correction:
1Create visited once before the outer loop.
2Never reset it during the scan.Incorrect line placement:
1for each vertex v in vertices:
2 componentCount <- componentCount + 1
3 if visited[v] = false:
4 markComponent(...)Exposing input:
1A: [B]
2B: [A, C]
3C: [B]The graph is one path, so it has one component.
Wrong result:
1componentCount = 3Correction:
1Increment componentCount only after confirming visited[v] = false.Incorrect helper:
1markComponent(v, id, ...):
2 visited[v] <- true
3 componentId[v] <- id
4 for each neighbor w:
5 if visited[w] = false:
6 markComponent(w, id, ...) without assigning id to wAn implementation may instead mark every reached vertex visited but assign an id only to the original traversal start.
Exposing input:
1A: [B]
2B: [A]Wrong state:
1componentId[A] = 1
2componentId[B] = unsetThen a same-component query cannot correctly compare A and B.
Correction:
1At the start of every DFS helper call, assign:
2componentId[v] <- id| Input | Expected result |
|---|---|
Vertices [A, B, C], no edges | componentCount = 3; all three identifiers are distinct. |
Path A-B-C-D | componentCount = 1; all four vertices share one identifier. |
| No vertices | componentCount = 0; identifier array is empty. |
Self-loop A-A and isolated B | componentCount = 2; A and B have different identifiers. |
Duplicate edge A-B listed twice | A and B still receive one shared identifier. |
For a self-loop, DFS sees A as its own neighbor after marking A visited, so it does not recurse again.
For a duplicate edge, DFS may inspect the repeated adjacency entry, but the second inspection finds the endpoint already visited.
Implement:
1connectedComponents(adjacencyList)It must return:
1(componentCount, componentId)The tests will verify:
1def connected_components(vertices, adj):
2 visited = {v: False for v in vertices} # one shared map, never reset
3 component_id = {}
4 count = 0
5
6 def mark_component(v, cid):
7 visited[v] = True
8 component_id[v] = cid
9 for w in adj[v]:
10 if not visited[w]:
11 mark_component(w, cid)
12
13 for v in vertices:
14 if not visited[v]: # a new component starts here
15 count += 1
16 mark_component(v, count)
17 return count, component_id
18
19vertices = ["A", "B", "C", "D", "E", "F"]
20adj = {"A": ["B"], "B": ["A", "C"], "C": ["B"], "D": ["E"], "E": ["D"], "F": []}
21count, ids = connected_components(vertices, adj)
22print("count:", count)
23print("ids:", " ".join(f"{v}={ids[v]}" for v in vertices))
24for u, v in [("A", "C"), ("B", "E")]:
25 print(f"same({u}, {v}):", "true" if ids[u] == ids[v] else "false")1import java.util.*;
2
3public class Main {
4 static Map<String, Integer> componentId = new HashMap<>();
5 static Set<String> visited = new HashSet<>(); // one shared set, never reset
6
7 static void markComponent(String v, int id, Map<String, List<String>> adj) {
8 visited.add(v);
9 componentId.put(v, id);
10 for (String w : adj.get(v)) {
11 if (!visited.contains(w)) markComponent(w, id, adj);
12 }
13 }
14
15 static int connectedComponents(List<String> vertices, Map<String, List<String>> adj) {
16 int count = 0;
17 for (String v : vertices) {
18 if (!visited.contains(v)) { // a new component starts here
19 count++;
20 markComponent(v, count, adj);
21 }
22 }
23 return count;
24 }
25
26 public static void main(String[] args) {
27 List<String> vertices = List.of("A", "B", "C", "D", "E", "F");
28 Map<String, List<String>> adj = new HashMap<>();
29 adj.put("A", List.of("B"));
30 adj.put("B", List.of("A", "C"));
31 adj.put("C", List.of("B"));
32 adj.put("D", List.of("E"));
33 adj.put("E", List.of("D"));
34 adj.put("F", List.of());
35
36 int count = connectedComponents(vertices, adj);
37 System.out.println("count: " + count);
38 StringBuilder sb = new StringBuilder();
39 for (String v : vertices) sb.append(sb.length() > 0 ? " " : "").append(v).append("=").append(componentId.get(v));
40 System.out.println("ids: " + sb);
41 System.out.println("same(A, C): " + componentId.get("A").equals(componentId.get("C")));
42 System.out.println("same(B, E): " + componentId.get("B").equals(componentId.get("E")));
43 }
44}1#include <iostream>
2#include <map>
3#include <string>
4#include <vector>
5using namespace std;
6
7map<string, vector<string>> adj;
8map<string, bool> visited; // one shared map, never reset
9map<string, int> componentId;
10
11void markComponent(const string& v, int id) {
12 visited[v] = true;
13 componentId[v] = id;
14 for (const string& w : adj[v]) {
15 if (!visited[w]) markComponent(w, id);
16 }
17}
18
19int main() {
20 vector<string> vertices = {"A", "B", "C", "D", "E", "F"};
21 adj = {{"A", {"B"}}, {"B", {"A", "C"}}, {"C", {"B"}}, {"D", {"E"}}, {"E", {"D"}}, {"F", {}}};
22 for (const string& v : vertices) visited[v] = false;
23
24 int count = 0;
25 for (const string& v : vertices) {
26 if (!visited[v]) { // a new component starts here
27 count++;
28 markComponent(v, count);
29 }
30 }
31
32 cout << "count: " << count << "\nids:";
33 for (const string& v : vertices) cout << " " << v << "=" << componentId[v];
34 cout << "\nsame(A, C): " << (componentId["A"] == componentId["C"] ? "true" : "false");
35 cout << "\nsame(B, E): " << (componentId["B"] == componentId["E"] ? "true" : "false") << endl;
36}1function connectedComponents(vertices, adj) {
2 const visited = new Map(vertices.map((v) => [v, false])); // one shared map, never reset
3 const componentId = new Map();
4 let count = 0;
5
6 function markComponent(v, id) {
7 visited.set(v, true);
8 componentId.set(v, id);
9 for (const w of adj.get(v)) {
10 if (!visited.get(w)) markComponent(w, id);
11 }
12 }
13
14 for (const v of vertices) {
15 if (!visited.get(v)) { // a new component starts here
16 count++;
17 markComponent(v, count);
18 }
19 }
20 return { count, componentId };
21}
22
23const vertices = ['A', 'B', 'C', 'D', 'E', 'F'];
24const adj = new Map([
25 ['A', ['B']],
26 ['B', ['A', 'C']],
27 ['C', ['B']],
28 ['D', ['E']],
29 ['E', ['D']],
30 ['F', []],
31]);
32const { count, componentId } = connectedComponents(vertices, adj);
33console.log(`count: ${count}`);
34console.log(`ids: ${vertices.map((v) => `${v}=${componentId.get(v)}`).join(' ')}`);
35for (const [u, v] of [['A', 'C'], ['B', 'E']]) {
36 console.log(`same(${u}, ${v}): ${componentId.get(u) === componentId.get(v)}`);
37}No. One DFS reaches only one component. On A-B and C-D, starting at A gives {A, B} and misses C and D. The outer loop over all vertices starts a new DFS at each unvisited one.
Yes. F in the example has no edges, but it is a vertex that reaches itself, so it is a component of size 1 with its own id.
Resetting it before each DFS makes finished vertices look new, so the same component is counted again. Create it once before the outer loop and never clear it.
Compare their ids after the scan. A and C both have id 1, so they are connected. B has 1 and E has 2, so they are not.
A graph is connected when it has exactly one component. The example has three, so it is not connected.