def find(data, i):
if i != data[i]:
data[i] = find(data, data[i])
return data[i]
def union(data, i, j):
pi, pj = find(data, i), find(data, j)
if pi != pj:
data[pi] = pj
def connected(data, i, j):
return find(data, i) == find(data, j)
n = 10
data = [i for i in range(n)]
connections = [(0, 1), (1, 2), (0, 9), (5, 6), (6, 4), (5, 9)]
# union
for i, j in connections:
union(data, i, j)
# find
for i in range(n):
print('item', i, '-> component', find(data, i))
item 0 -> component 9 item 1 -> component 9 item 2 -> component 9 item 3 -> component 3 item 4 -> component 9 item 5 -> component 9 item 6 -> component 9 item 7 -> component 7 item 8 -> component 8 item 9 -> component 9