Count Connected Components with Union-Find
Count connected components in an undirected graph using a disjoint-set structure.
Example check: Worked and guided code samples are checked against CPython 3.13. Practice uses Pyodide 0.29.5 (Python 3.13) in your browser. How we check lessons
Video lesson: Count Connected Components with Union-Find
The preview is stored on this site. YouTube loads only when you press Play. Watch on YouTube
Jump to a chapter
Read the video transcript
Select a timestamp to watch that moment on YouTube.
- 00:00
A, B and C form a triangle; D stands alone. Run edge counting. Will three edges imply one connected component, or does one triangle edge change nothing? The broken formula starts with four nodes and subtracts three edges, printing one. But A-C is redundant after A-B and B-C have already merged those nodes. D is still isolated. An input row is not necessarily a successful merge, especially in a cycle or duplicate-edge list. Check each undirected edge against the current groups. Before any edges, A, B, C, and D are four components. A-B reduces that to three.
- 00:40
B-C reduces it to two. A-C stays entirely within the first group, so the count remains two. The broken shortcut subtracts every row, even the redundant closing edge, and prints one. It cannot distinguish a tree edge from a cycle edge, so duplicate input rows would make its answer even less reliable. A component count cannot be inferred from edge count alone because many edges may be internal to an existing group. A square with a diagonal has even more redundant edges but still only one component among its four vertices. Conversely, D can remain isolated with no incident edge and still contributes one component.
- 01:22
The broken formula forgets both facts. Successful merges, rather than raw edge rows, are the meaningful event to count. The diagnosis prints roots A and D after useful merges and confirms that A-C are already joined. The two roots correspond to two components. Union-find locates a representative root for each endpoint; if they match, the new edge has no effect on the component count. After joining A and B, finding either name yields one representative. Joining B and C brings C under that representative too. For A-C, find returns the same root at both ends, and union reports that nothing changed.
- 02:04
The diagnosis prints roots A and D, which directly count the two components. D matters even though it appears in no edge: we had to initialize every declared node, not just names encountered while processing connections. Roots are representative labels, not an ordered list of all members. After path compression, parent pointers may change while connectivity stays the same. That means tests should compare whether find returns the same root for connected nodes, or compare component counts, rather than assert an exact internal parent dictionary for every implementation. The captured roots A and D are one possible stable representation of this
- 02:44
tiny example. Try five declared nodes A through E. Join A with B and C with D: the count falls from five to four, then three, while E remains alone. The edge B-C is a bridge between two roots, so it falls to two. An additional A-D row sits inside the already merged group and must leave the count at two. This sequence shows why the input order may change intermediate roots but cannot change final connectivity. The fixed function initializes every declared node, including D. Each successful union reduces the count by one, while repeated or cycle-closing edges leave it alone.
- 03:25
Path compression shortens future root lookups. The terminal prints two components for the triangle plus isolated D. Follow the parent dictionary as a forest of rooted trees. find walks upward until parent at a root points to itself. Path compression then rewrites a node's parent to that root, shortening future walks. To merge an edge, compare endpoint roots and link one root to the other only if they differ. Decrement the count on that successful link. The terminal prints two because exactly two of the three triangle edges made a new connection. A useful invariant is declared node count minus the number of successful unions.
- 04:06
For the five-node example, three successful unions leave two components, regardless of how many redundant edges were also supplied. Test that invariant after every insert, not just at the final print. On a tiny graph, a separate depth-first traversal can count groups slowly and serve as an oracle for randomized edge lists. Comparing the two catches mistakes in parent updates that a fixed triangle may miss. The verifier prints zero components for an empty graph, four for four isolated nodes, and one for a graph where all supplied nodes connect. Duplicate and self-loop edges should not decrement the answer.
- 04:46
Union-find supports edges being added; removing an edge and asking for fresh connectivity needs another method. The empty-node case has zero groups, even though there are also zero edges. The connected example has one group after its useful merges. An edge from a node to itself and a repeated A-B edge leave roots unchanged and must not reduce the count again. In this compact function an unknown endpoint raises KeyError at the parent lookup; validate it explicitly for a clearer error. Union-find answers connectivity as edges are added, not after arbitrary edge removal. If all four nodes are declared but no edges are present, the correct result is
- 05:28
four. If the node list itself is empty, the correct result is zero. Those cases differ even though both inputs have no edges. Duplicate edges also matter for data imported from logs: the count must not fall below the true number of groups just because the same connection was recorded twice. Consider a chain A-B-C. After both edges are added, union-find correctly says one component. If the B-C edge is later deleted, the correct answer becomes two, but the old parent forest still records C as connected. Path compression cannot undo that history.
- 06:08
For occasional deletions, rebuild from the remaining edges; for heavy dynamic updates, choose a data structure designed for them. This concrete deletion case defines the boundary of the insert-only tool shown here.
Understand the concept
A network contains nodes A, B, C and D. The first three form a triangle, while D is isolated. Counting components requires knowing which nodes are already connected. Union-find stores a parent for each node and merges only when an edge joins two previously separate groups.
Starting with one component per node and subtracting the number of edges gives the wrong answer for a cycle. The triangle has three edges but only two useful merges; its third edge connects nodes already in the same component. The broken calculation reports one component instead of two and nearly hides isolated D.
Trace root representatives after each edge. A-B merges two groups, B-C merges another, and A-C finds the same root on both ends so it does nothing. D remains its own root. Count successful unions, not edges, or count distinct representatives after processing. Initialize parent[node] = node for every declared node, including isolated ones. A find function follows parent links and compresses paths. Union roots for each undirected edge, decrementing the component count only when the roots differ. In this compact demo an unknown edge endpoint raises KeyError from the parent lookup; validate endpoints explicitly if the caller needs a friendlier error.
An empty graph has zero components, and four isolated nodes have four. A duplicate or self-loop edge should not reduce the count. The final run checks these cases so the result reflects connectivity rather than the number of input rows. This small implementation uses path compression and is adequate for the exercise. For very large dynamic graphs, union by rank or size can further control tree height. Union-find answers connectivity under added edges; removing edges requires another strategy.
- A network contains nodes A, B, C and D.
- Starting with one component per node and subtracting the number of edges gives the wrong answer for a cycle.
- Initialize parent[node] = node for every declared node, including isolated ones.
- An empty graph has zero components, and four isolated nodes have four.
See it step by step
Read the code, predict the output, then compare it with the result.
01. See why edge count fails
nodes=['A','B','C','D']; edges=[('A','B'),('B','C'),('A','C')]
print(len(nodes)-len(edges))
print('D isolated:', all('D' not in edge for edge in edges))
1
D isolated: TrueThree edges do not imply three successful group merges.
02. Track roots after the triangle
parent={'A':'A','B':'A','C':'A','D':'D'}
print(sorted(set(parent.values())))
['A', 'D']The triangle has one representative and D has another.
03. Skip a redundant merge
roots={'A':'A','B':'A','C':'A','D':'D'}
left,right='A','C'
print(roots[left] == roots[right])
TrueAn edge within an existing component changes nothing.
A closer look
Follow the reasoning, inspect each result, then try the suggested changes in the console below.
Observe the first result
A network contains nodes A, B, C and D. The first three form a triangle, while D is isolated. Counting components requires knowing which nodes are already connected. Union-find stores a parent for each node and merges only when an edge joins two previously separate groups.
Three edges do not imply three successful group merges. Trace root representatives after each edge. A-B merges two groups, B-C merges another, and A-C finds the same root on both ends so it does nothing. D remains its own root. Count successful unions, not edges, or count distinct representatives after processing.
nodes=['A','B','C','D']; edges=[('A','B'),('B','C'),('A','C')]
print(len(nodes)-len(edges))
print('D isolated:', all('D' not in edge for edge in edges))
1
D isolated: True- Predict the first sample's printed value and type.
- Run it, then compare with the expected output.
Change the rule deliberately
Starting with one component per node and subtracting the number of edges gives the wrong answer for a cycle. The triangle has three edges but only two useful merges; its third edge connects nodes already in the same component. The broken calculation reports one component instead of two and nearly hides isolated D.
The triangle has one representative and D has another. Initialize parent[node] = node for every declared node, including isolated ones. A find function follows parent links and compresses paths. Union roots for each undirected edge, decrementing the component count only when the roots differ. In this compact demo an unknown edge endpoint raises KeyError from the parent lookup; validate endpoints explicitly if the caller needs a friendlier error. Initialize a parent for every node. Find both roots for each edge and decrement count only if roots differ.
parent={'A':'A','B':'A','C':'A','D':'D'}
print(sorted(set(parent.values())))
['A', 'D']- Identify the line that changes the rule.
- Run the corrected sample with the same input.
Verify the boundary
Trace root representatives after each edge. A-B merges two groups, B-C merges another, and A-C finds the same root on both ends so it does nothing. D remains its own root. Count successful unions, not edges, or count distinct representatives after processing. Initialize parent[node] = node for every declared node, including isolated ones. A find function follows parent links and compresses paths. Union roots for each undirected edge, decrementing the component count only when the roots differ. In this compact demo an unknown edge endpoint raises KeyError from the parent lookup; validate endpoints explicitly if the caller needs a friendlier error.
An edge within an existing component changes nothing. An empty graph has zero components, and four isolated nodes have four. A duplicate or self-loop edge should not reduce the count. The final run checks these cases so the result reflects connectivity rather than the number of input rows. This small implementation uses path compression and is adequate for the exercise. For very large dynamic graphs, union by rank or size can further control tree height. Union-find answers connectivity under added edges; removing edges requires another strategy.
roots={'A':'A','B':'A','C':'A','D':'D'}
left,right='A','C'
print(roots[left] == roots[right])
True- Try the documented edge case.
- Explain why the output satisfies the function contract.
Try it in Python
Edit the example and run it. Python starts in your browser the first time you click Run.
Python console
Ready to runNeed input()? Add one value per line
Your output appears here.
Need a hint?
Initialize a parent for every node. Find both roots for each edge and decrement count only if roots differ.
Complete the task and select Check task to verify your code.
Quick quiz
Three questions. You can change your answers and try again.
Typical mistakes
Everyone meets these errors. See what causes them and how to fix them.
The visible failure
len(nodes) - len(edges)decrement only when union joins two different rootsWhat happens: Starting with one component per node and subtracting the number of edges gives the wrong answer for a cycle.
Initialize parent[node] = node for every declared node, including isolated ones. A find function follows parent links and compresses paths. Union roots for each undirected edge, decrementing the component count only when the roots differ. In this compact demo an unknown edge endpoint raises KeyError from the parent lookup; validate endpoints explicitly if the caller needs a friendlier error.
Missing the edge condition
initialize parents from edge endpoints onlyinitialize parents for every declared nodeWhat happens: An empty graph has zero components, and four isolated nodes have four.
This small implementation uses path compression and is adequate for the exercise. For very large dynamic graphs, union by rank or size can further control tree height. Union-find answers connectivity under added edges; removing edges requires another strategy.