Start with everyone alone, count down

How many friend circles are there in a class, given who's friends with whom? Everyone starts as a circle of one, so the count starts at n, the number of people.

Each merge of two different groups turns two circles into one, so the count goes down by 1. A merge between two people who are already in the same group changes nothing, so don't count it.

Start at n: everyone is alone.

Different leaders? merge, and the count drops by 1.

5 people, merged 0–1, 1–2, 3–4

groups: 5

5 people, 5 groups of one. Start the count at 5.

Move 1 of 5

The same question in many disguises

"How many friend circles?", "how many separate islands?", "how many clusters of servers?" all turn into this once you see them as a list of merges followed by a count.

For 5 people with merges 0-1, 1-2 and 3-4, you end with 2 groups: 0, 1, 2 together, and 3, 4 together.

Spot it: a list of connections in, a number of groups out.

In code

parent = list(range(n))
def find(x):
    while parent[x] != x:
        x = parent[x]
    return x
groups = n
for a, b in edges:
    ra, rb = find(a), find(b)
    if ra != rb:
        parent[ra] = rb
        groups -= 1
return groups