并查集

并查集的典型题目有朋友圈问题

A和B是好友，B和C是好友则A和C也是好友，他们构成一个朋友圈，问一共有多少个朋友圈

'''

并查集主要包含几个操作

1.查找根节点

2.连接根节点

3.压缩路径的话就添加一个rank数组，代表当前node的深度

'''

#coding:utf-8

class Disjoint:

    #初始化parent数组

    def __init__(self,n):

        self.parent = []

        for i in range(n):

            self.parent.append(-1)

    #找到某一个结点的最终根节点   

    def find_root(self,node):

        #只要它的根节点不是-1，就一直往上搜寻

        while self.parent[node] != -1:

            node = self.parent[node]

        #此时的node就是node的最终根节点   

        return node

    #连接两棵树的顶点

    #如果返回1，则代表表连接成功

    #如果返回0，则代表连接失败，当两个节点已经在同一个集合里的时候就会连接失败

    def union_vertices(self,node1,node2):

        node1_root = self.find_root(node1)

        node2_root = self.find_root(node2)

        #如果node1_root和node2_root是同一个节点，那么代表node1和node2的最终根节点是同一个，他们在一个集合里，合并失败

        if node1_root == node2_root:

            return 0

        else:

            self.parent[node1_root] = node2_root

            return 1

if __name__ == "__main__":

    edge = [[0,1],[0,2],[1,4],[4,3],[4,5],[3,5],[6,7],[7,8]]

    D = Disjoint(9)

    for item in edge:

        D.union_vertices(item[0],item[1])

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

最后输出的是parent数组中的    -1的个数就是朋友圈个数