To merge groups we join their roots. Implement union(a, b): find the root of a and the root of b; if they differ, attach the root of b under the root of a by setting parent of root_b to root_a.
After a union, any two items in the merged set share the same root, which find will report.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
while self.parent[x] != x:
x = self.parent[x]
return x
def union(self, a, b):
"""Merge the sets containing a and b."""
# TODO: find both roots; if they differ, attach root of b under root of a.
pass
The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.
To merge groups we join their roots. Implement union(a, b): find the root of a and the root of b; if they differ, attach the root of b under the root of a by setting parent of root_b to root_a.
After a union, any two items in the merged set share the same root, which find will report.
Press Run Tests or ⌘↩ to check your solution.