How many separate groups does a network have?

Graphs Mid-level Python 3.13+ Reviewed 1 Nov 2026 By Best Latest Apps

Predict the output

What does this print?

Python 3.13

boss = list(range(5))

def find(x: int) -> int:
    while boss[x] != x:
        boss[x] = boss[boss[x]]
        x = boss[x]
    return x

for a, b in [(0, 1), (1, 2), (3, 4)]:
    boss[find(a)] = find(b)
print(len({find(x) for x in range(5)}))

Options235

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 2

Right: {0, 1, 2} and {3, 4}.

Every successful join removes one group, and the three links here make three joins.

Why not the others?

B 3. Three links join five computers into two groups.
C 5. Each link merges two groups, so the count drops.

30-second answer

Union-find: start with every computer in its own group, and for each link join the two groups if they differ, subtracting one from the count. With path compression and union by size, each operation is nearly O(1), so the whole thing is O(n + E·α(n)) time, with O(n) space for the two arrays.

Practise saying it · 45 s. No recording, just a timer

Explain union-find for counting groups.

Say your answer out loud, then check which of these points you covered:

Each node starts alone
Join roots, count down
Near O(1) per operation

Deep dive

DFS or BFS from each unvisited node gives the same count in O(V + E).

Union-find wins when links arrive over time and you need the count after each one.

find with path halving (boss[x] = boss[boss[x]]) is a short, iterative form of path compression.

Python solution Ran on Python 3.13.5 · mypy --strict

Python 3.13

def count_groups(n: int, links: list[list[int]]) -> int:
    boss = list(range(n))
    size = [1] * n

    def find(x: int) -> int:
        while boss[x] != x:
            boss[x] = boss[boss[x]]
            x = boss[x]
        return x

    groups = n
    for a, b in links:
        ra, rb = find(a), find(b)
        if ra == rb:
            continue
        if size[ra] < size[rb]:
            ra, rb = rb, ra
        boss[rb] = ra
        size[ra] += size[rb]
        groups -= 1
    return groups

Common mistakes

Forgetting isolated computers with no links; they are groups too.
Joining by setting boss[a] = b instead of joining the two roots.

Senior take & follow-ups

Write find and union as small helpers; it reads cleanly and shows you know the structure.

Follow-up questions

Think of your answer first, then open the hint.

What does union by size buy you?
Show hint
It keeps trees shallow, O(log n) even without compression.
How would you tell if the network is a single tree?
Show hint
Exactly n - 1 links and one group at the end.

What each operation costs: Breadth First Search · Depth First Search · Topological Sort · Dijkstra Algorithm

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.