Largest group
Track each root's group size alongside parent, and add sizes together whenever two groups merge. About 8 minutes.
The leader keeps the headcount
Now you also want to know how big each group is. Give every person a size, starting at 1: a group of one.
Only the leader's size matters. When two groups merge, the new leader adds the other leader's size to its own. The old leader's size is simply never looked at again, like a club secretary handing over the membership list.
Everyone is a group of 1.
Sizes add up, never overwrite
When groups of 2 and 3 merge, the new group has 5 people. The sizes add. When every merge is done, the biggest size held by any leader is the answer.
For 5 people with merges 0-1, 1-2 and 3-4, the leaders hold sizes 3 and 2, so the answer is 3.
parent = list(range(n))
size = [1] * n
def find(x):
while parent[x] != x:
x = parent[x]
return x
for a, b in edges:
ra, rb = find(a), find(b)
if ra != rb:
parent[ra] = rb
size[rb] += size[ra]
return max(size[find(i)] for i in range(n))Groups of 1, 1 and 2 people all merge into one group. How big is it?
- A4
- B2
Show the answer
4. 1 + 1 + 2 = 4. Merging adds the sizes together.
Largest group
There are n people, numbered 0 to n - 1, each starting alone. edges lists pairs [a, b] meaning a and b's groups are merged, in order. Return the size of the largest group once every merge in edges has happened.
n = 5, edges = [[0, 1], [1, 2], [3, 4]] → 3
1 ≤ n ≤ 1,000 · 0 ≤ edges.length ≤ 1,000 · edges[i] has two different node numbers, each 0 ≤ x < n