Where it runs
1. The problem
You have a class of students and a list of who is friends with whom. Some friendships link up into one big group. A few students are friends as a trio, apart from everyone else. One student knows nobody. The question: how many separate friend circles are there in the class?
Counting islands on a map and finding the separate clusters of a network work the same way. You have a graph (dots joined by lines), and it may consist of several pieces. No edge runs between two pieces. You want to know how many pieces there are.
In the BFS and DFS lessons you walked a graph from one start. One walk reaches every node of its own piece and no node of any other piece. So there are as many pieces as the walks you need to visit every node.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedcountComponents(7, {0: [1, 2], 1: [0, 2], 2: [0, 1], 3: [4], 4: [3, 5], 5: [4], 6: []})Count the separate groups among 7 nodes. One visited set is kept for the whole run and is never reset.
Recognise it
Say these words and it is this pattern
- count separate groups/islands/clusters
- graph may be disconnected
- how many connected pieces
- friend circles
- label connected regions
Looks similar, isn't
- Graph BFS / DFS
That is the walk itself. This page is the loop that starts one walk per group.
- Union-find (disjoint set)
Union-find answers while the edges are still arriving. Flood fill needs the whole graph up front.
- Bipartite check (two-coloring)
A two-colouring runs the same walk while carrying a colour. It answers a different question.
- Topological sort (Kahn's algorithm)
Ordering needs directed edges and no cycles. Components treat every edge as undirected.
V nodes and E edges give O(V + E) in total. Each node is visited by exactly one walk.
On LeetCode
Problems that count separate groups, such as islands, friend circles or networks. Loop over every node, and each node not yet visited starts a new group that one walk marks whole.
The lesson's countComponents, with the graph given as an adjacency matrix.
Each unvisited land cell starts a new island, and a walk marks all of its land.
The same loop, where each walk returns the size of its group and you keep the largest.
Walk each island of grid2 and count it only if every cell it covers is land in grid1 too.