Free lessonsUnion-find · Stage 0 · Groups that merge · Step 2

Count the groups

Start with n groups, and lose one every time a merge actually joins two different groups. About 7 minutes.

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

Quick check

4 people. Merges happen in this order: 0 with 1, 2 with 3, then 1 with 2. How many groups are left?

Show the answer

1. 0-1 leaves 3 groups, 2-3 leaves 2, and 1-2 joins those two into one.

Your problem

Count the groups

There are n people, numbered 0 to n - 1, each starting in their own group. edges lists pairs [a, b] meaning a and b's groups are merged, in order. Return how many separate groups remain after every merge in edges.

Example

n = 5, edges = [[0, 1], [1, 2], [3, 4]] → 2

1 ≤ n ≤ 1,000 · 0 ≤ edges.length ≤ 1,000 · edges[i] has two different node numbers, each 0 ≤ x < n

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.

Start coding