python----并查集，,Quick Find

python----并查集，,Quick Find

Quick Find

# -*- coding: utf-8 -*-class QuickFind(object):    id = []    cnt = 0  # the number of the sets    def __init__(self, n):        self.cnt = n        for i in range(0, n):            self.id.append(i)    def connected(self, p, q):        return self.find(p) == self.find(q)    def find(self,p):        return self.id[p]    def union(self,p,q):        id_p = self.find(p)        if not self.connected(p,q):            for i in range(0,len(self.id)):                if self.id[i] == id_p:                    self.id[i] = self.id[q]  #combine            self.cnt -= 1qf = QuickFind(10)print("initial id list is %s" % (‘,‘).join(str(x) for x in qf.id))list = [        (4,3),        (3,8),        (6,5),        (9,4),        (2,1),        (8,9),        (5,0),        (7,2),        (6,1),        (1,0),        (6,7)        ]for edge in list :    p = edge[0]    q = edge[1]    qf.union(p,q)    print("%d and %d is connected? %s"%(p,q,str(qf.connected(p,q))))print("final id list is %s" %(",").join(str(x) for x in qf.id))print("count of sets is : %d" % qf.cnt)

connect更新的时候需要遍历，可以借用树结构来减小时间复杂度。

# -*- coding: utf-8 -*-class QuickUnion(object):    id = []    cnt = 0  # the number of the sets    def __init__(self, n):        self.cnt = n        for i in range(0, n):            self.id.append(i)    def connected(self, p, q):        return self.find(p) == self.find(q)    def find(self,x):        while(x != self.id[x]):            x = self.id[x]        return x    def union(self,p,q):        root_p = self.find(p)        root_q = self.find(q)        if not self.connected(p,q):            self.id[root_p] = root_q            self.cnt -= 1    qu = QuickUnion(10)print("initial id list is %s" % (‘,‘).join(str(x) for x in qf.id))list = [        (4,3),        (3,8),        (6,5),        (9,4),        (2,1),        (8,9),        (5,0),        (7,2),        (6,1),        (1,0),        (6,7)        ]for edge in list :    p = edge[0]    q = edge[1]    qu.union(p,q)    print("%d and %d is connected? %s"%(p,q,str(qu.connected(p,q))))print("final id list is %s" %(",").join(str(x) for x in qu.id))print("count of sets is : %d" % qu.cnt)

Weighted Quick Union

Quick Union 可能会退化成链，导致性能下降，可以通过Weighted Quick Union尽量平衡树的高度，从而提升性能。

# -*- coding: utf-8 -*-class WeightedQuickUnion(object):    id = []    cnt = 0  # the number of the sets    sz = []    def __init__(self, n):        self.cnt = n        for i in range(0, n):            self.id.append(i)            self.sz.append(1)    def connected(self, p, q):        return self.find(p) == self.find(q)    def find(self,x):        while(x != self.id[x]):            x = self.id[x]        return x    def union(self,p,q):        root_p = self.find(p)        root_q = self.find(q)        if not self.connected(p,q):            if self.sz[q] > self.sz[p]:    #保证小树连大树，若大树连小树可能退化成链                self.id[root_p] = root_q                self.cnt -= 1                self.sz[q] += self.sz[p]            else :                self.id[root_q] = root_p                self.cnt -= 1                self.sz[p] += self.sz[q]wqu = WeightedQuickUnion(10)print("initial id list is %s" % (‘,‘).join(str(x) for x in wqu.id))list = [        (4,3),        (3,8),        (6,5),        (9,4),        (2,1),        (8,9),        (5,0),        (7,2),        (6,1),        (1,0),        (6,7)        ]for edge in list :    p = edge[0]    q = edge[1]    wqu.union(p,q)    print("%d and %d is connected? %s"%(p,q,str(wqu.connected(p,q))))print("final id list is %s" %(",").join(str(x) for x in wqu.id))print("count of components is : %d" % wqu.cnt)

可通过压缩查找进一步提升性能，类似树桩。

参考：http://www.cnblogs.com/learnbydoing/p/6896472.html?utm_source=itdadao&utm_medium=referral

python----并查集