Are they in the same group?
Every node starts in its own group; keep a parent array and follow it up to find each group's root. About 9 minutes.
Merging means one leader follows another
To merge the groups of two people, find each one's leader, then make one leader point to the other. That's it. Every member of both groups now leads back to the same leader, so they're all one group.
If both people already have the same leader, they're in the same group and there's nothing to do.
Merge everything, then answer
Process every merge in order. Then, to answer "are these two in the same group?", find each person's leader and compare. Step through the picture: after 0 joins 1 and 1 joins 2, following the arrows from 0 leads to 2, and so does 2 itself. Same leader, same group.
Person 3 was never merged with them, so 3 is still its own leader.
parent = list(range(n))
def find(x):
while parent[x] != x:
x = parent[x]
return x
for a, b in edges:
parent[find(a)] = find(b)
return find(query[0]) == find(query[1])- parent
- [0, 1, 2, 3, 4]
Everyone starts on their own, pointing at themselves, so there are no arrows yet. Each person is their own leader.
0 joins 1, then 1 joins 2. Are 0 and 3 in the same group?
- ANo
- BYes, because 0 has been merged
Show the answer
No. 0, 1 and 2 are one group, but 3 was never merged with anyone, so it's still on its own.
Are they in the same group?
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. After every merge in edges has happened, return true if the people in query are in the same group, or false otherwise.
n = 5, edges = [[0, 1], [1, 2], [3, 4]], query = [0, 2] → true
1 ≤ n ≤ 1,000 · 0 ≤ edges.length ≤ 1,000 · edges[i] has two different node numbers, each 0 ≤ x < n · query.length == 2