Number of Connected Components in an Undirected Graph
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Given n nodes and undirected edges, count the connected components (separate groups).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1If there are no edges, how many components are there?
- Hint 2What happens to the count when an edge joins two nodes already in the same group?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Friend circles at a school. At first each of the n students is alone: n circles. Each new friendship either joins two different circles (the number of circles drops by one) or links two kids who are already in the same circle (nothing changes). After all friendships the number left is the number of circles.
- The obvious way
DFS/BFS from each unvisited node, counting starts: also O(n + edges).
- The key insight
components = n. For each edge find the heads of both ends; if different, point one head at the other and subtract one from components. Return components.
- The algorithm
- components = n; each node is its own head.
- For each edge: find both heads.
- Different heads: merge, components - 1.
- Return components.
Watch it run
Examplen = 5, edges = [[0,1],[1,2],[3,4]]
Five students, five circles.
components = 5
Where people slip
- Compare heads (the group identity), not the nodes, before merging.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def count_components(n, edges):
head = list(range(n)) # every student is their own head
def find(student):
while head[student] != student:
head[student] = head[head[student]]
student = head[student]
return student
circles = n
for first, second in edges:
first_head, second_head = find(first), find(second)
if first_head != second_head:
head[first_head] = second_head # two circles become one
circles -= 1
return circlesNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.