并查集计算相似文件的类别数(朋友圈个数)

# -*- coding:utf-8 -*-

def find_root(x, parent):
    xroot = x
    while parent[xroot] != -1:
        xroot = parent[xroot]
    return xroot

def union_vertex(x, y, parent):
    xroot = find_root(x, parent)
    yroot = find_root(y, parent)
    if xroot != yroot:
        parent[xroot] = yroot

def init_parent(edges):
    nodes = []
    for item in edges:
        nodes.extend(item)
    parent = [-1] * len(set(nodes))
    return parent

edges = [[0,1],[2,3],[3,4],[4,5],[5,1],[6,7]]
parent = init_parent(edges)

for pair in edges:
    x = pair[0]
    y = pair[1]
    union_vertex(x, y, parent)

print(parent)
print(parent.count(-1))