面试常考算法题之并查集问题

摘要：很显然，我们可以使用并查集来求解。并查集是用来将一系列的元素分组到不相交的集合中，并支持合并和查询操作。理论总是过于抽象化，下面我们通过一个例子来说明并查集是如何运作的。采用这个方法，我们就可以写出最简单版本的并查集代码。

朋友圈问题

现在有 105个用户，编号为 1- 105。已知有 m 对关系，每一对关系给你两个数 x 和 y ，代表编号为 x 的用户和编号为 y 的用户是在一个圈子中，例如： A 和 B 在一个圈子中， B 和 C 在一个圈子中，那么 A , B , C 就在一个圈子中。现在想知道最多的一个圈子内有多少个用户。

数据范围：1<= m <= 2 * 10 6 。

进阶：空间复杂度 O（n），时间复杂度 O（nlogn）。

输入描述:

第一行输入一个整数T，接下来有T组测试数据。对于每一组测试数据：第一行输入1个整数n，代表有n对关系。接下来n行，每一行输入两个数x和y，代表编号为x和编号为y的用户在同一个圈子里。

1 ≤ T ≤ 10

1 ≤ n ≤ 2 * 106

1 ≤ x, y ≤ 105

输出描述:

对于每组数据，输出一个答案代表一个圈子内的最多人数。

示例：

输入：

241 23 45 61 641 23 45 67 8

输出：

42

分析问题

通过分析题目，我们可以知道，这道题是求元素分组的问题，即将所有用户分配到不相交的圈子中，然后求出所有圈子中人数最多的那个圈子。

很显然，我们可以使用并查集来求解。

首先，我们来看一下什么是并查集。

并查集是用来将一系列的元素分组到不相交的集合中，并支持合并和查询操作。

• 合并（Union）：把两个不相交的集合合并为一个集合。
• 查询（Find）：查询两个元素是否在同一个集合中。

并查集的重要思想在于，用集合中的一个元素代表集合。

理论总是过于抽象化，下面我们通过一个例子来说明并查集是如何运作的。

我们这里把集合比喻成帮派，而集合中的代表就是帮主。

一开始，江湖纷争四起，所有大侠各自为战，他们每个人都是自己的帮主（对于只有一个元素的集合，代表元素自然就是唯一的那个元素）。

有一天，江湖人士张三和李四偶遇，都想把对方招募到麾下，于是他们进行了一场比武，结果张三赢了，于是把李四招募到了麾下，那么李四的帮主就变成了张三（合并两个集合，帮主就是这个集合的代表元素）。

然后，李四又和王五偶遇，两个人互相不服，于是他们进行了一场比武，结果李四又输了（李四怎么那么菜呢），此时李四能乖乖认怂，加入王五的帮派吗？那当然是不可能！！ 此时的李四已经不再是一个人在战斗，于是他呼叫他的老大张三来，张三听说小弟被欺负了，那必须收拾他！！于是和王五比试了一番，结果张三赢了，然后把王五也拉入了麾下（其实李四没必要和王五比试，因为李四比较怂，直接找大哥来收拾王五即可）。此时王五的帮主也是张三了。

我们假设张三二，李四二也进行了帮派的合并，江湖局势变成了如下的样子，形成了两大帮派。

通过上图，我们可以知道，每个帮派（一个集合）是一个树状的结构。

要想寻找到集合的代表元素（帮主），只需要一层层往上访问父节点，直达树的根节点即可。其中根节点的父节点是它自己。

采用这个方法，我们就可以写出最简单版本的并查集代码。

1. 初始化

   我们用数组 fa 来存储每个元素的父节点（这里每个元素有且只有一个父节点）。一开始，他们各自为战，我们将它们的父节点设为自己（假设目前有编号为1~n的n个元素）。

    def __init__(self,n):        self.fa=[0]*(n+1)        for i in range(1,n+1):            self.fa[i]=i

2. 查询

   这里我们使用递归的方式查找某个元素的代表元素，即一层一层的访问父节点，直至根节点（根节点是指其父节点是其本身的节点）。

    def find(self,x):        if self.fa[x]==x:            return x        else:            return self.find(self.fa[x])

3. 合并

   我们先找到两个元素的根节点，然后将前者的父节点设为后者即可。当然也可以将后者的父节点设为前者，这里暂时不重要。后面会给出一个更合理的比较方法。

       def merge(self,x,y):        x_root=self.find(x)        y_root=self.find(y)        self.fa[x_root]=y_root

整体代码如下所示。

class Solution(object):    def __init__(self,n):        self.fa=[0]*(n+1)        for i in range(1,n+1):            self.fa[i]=i    def find(self,x):        if self.fa[x]==x:            return x        else:            return self.find(self.fa[x])    def merge(self,x,y):        x_root=self.find(x)        y_root=self.find(y)        self.fa[x_root]=y_root

优化

上述最简单的并查集代码的效率比较低。假设目前的集合情况如下所示。

此时要调用merge(2,4)函数，于是从2找到1，然后执行f[1]=4，即此时的集合情况变成如下形式。

然后我们执行merge(2,5)函数，于是从2找到1，然后找到4，最后执行f[4]=5，即此时的集合情况变成如下形式。

一直执行下去，我们就会发现该算法可能会形成一条长长的链，随着链越来越长，我们想要从底部找到根节点会变得越来越难。

所以就需要进行优化处理，这里我们可以使用路径压缩的方法，即使每个元素到根节点的路径尽可能的短。
具体来说，我们在查询的过程中，把沿途的每个节点的父节点都设置为根节点即可。那么下次再查询时，就可以很简单的获取到元素的根节点了。代码如下所示：

    def find(self,x):        if x==self.fa[x]:            return x        else:            self.fa[x] = self.find(self.fa[x])            return self.fa[x]

经过路径压缩后，并查集代码的时间复杂度已经很低了。

下面我们再来进一步的进行优化处理---按秩合并。

这里我们需要先说明一点，因为路径压缩优化只是在查询时进行的，也只能压缩一条路径，因此经过路径优化后，并查集最终的结构仍然可能是比较复杂的。假设，我们现在有一颗比较复杂的树和一个元素进行合并操作。

如果此时我们要merge(1，6)，我们应该把6的父节点设为1。因为如果把1的父节点设为6，会使树的深度加深，这样就会使树中的每个元素到根节点的距离都变长了，从而使得之后我们寻找根节点的路径也就会相应的变长。而如果把6的父节点设为1，就不会出现这个问题。

这就启发我们应该把简单的树往复杂的树上去合并，因为这样合并后，到根节点距离变长的节点个数比较少。

具体来说，我们用一个数组rank 来记录每个根节点对应的树的深度（如果对应元素不是树的根节点，其rank值相当于以它作为根节点的子树的深度）。

初始时，把所有元素的rank设为1。在合并时，比较两个根节点，把rank较小者往较大者上合并。

下面我们来看一下代码的实现。

    def merge(self,x,y):        #找个两个元素对应的根节点        x_root=self.find(x)        y_root=self.find(y)                if self.rank[x_root] <= self.rank[y_root]:            self.fa[x_root]=y_root        else:            self.fa[y_root] = x_root                #如果深度相同且根节点不同，则新的根节点的深度        if self.rank[x_root] == self.rank[y_root] /                and x_root != y_root:           self.rank[y_root]=self.rank[y_root]+1

所以，我们终极版的并查集代码如下所示。

class Solution(object):    def __init__(self,n):        self.fa=[0]*(n+1)        self.rank=[0]*(n+1)        for i in range(1,n+1):            self.fa[i]=i            self.rank[i]=i    def find(self,x):        if x==self.fa[x]:            return x        else:            self.fa[x] = self.find(self.fa[x])            return self.fa[x]    def merge(self,x,y):        #找个两个元素对应的根节点        x_root=self.find(x)        y_root=self.find(y)        if self.rank[x_root] <= self.rank[y_root]:            self.fa[x_root]=y_root        else:            self.fa[y_root] = x_root        #如果深度相同且根节点不同，则新的根节点的深度        if self.rank[x_root] == self.rank[y_root] /                and x_root != y_root:           self.rank[y_root]=self.rank[y_root]+1

有了并查集的思想，那我们这道朋友圈的问题就迎刃而解了。下面我们给出可以AC的代码。

class Solution(object):    def __init__(self,n):        self.fa=[0]*(n+1)        self.rank=[0]*(n+1)        self.node_num=[0]*(n+1)        for i in range(1,n+1):            self.fa[i]=i            self.rank[i]=1            self.node_num[i]=1    def find(self,x):        if x==self.fa[x]:            return x        else:            self.fa[x] = self.find(self.fa[x])            return self.fa[x]    def merge(self,x,y):        #找个两个元素对应的根节点        x_root=self.find(x)        y_root=self.find(y)        if self.rank[x_root] <= self.rank[y_root]:            #将x_root集合合并到y_root上            self.fa[x_root]=y_root            self.node_num[y_root] = self.node_num[y_root] + self.node_num[x_root]        else:            #将y_root集合合并到x_root上            self.fa[y_root] = x_root            self.node_num[x_root] = self.node_num[x_root] + self.node_num[y_root]        #如果深度相同且根节点不同，则新的根节点的深度        if self.rank[x_root] == self.rank[y_root] /                and x_root != y_root:           self.rank[y_root]=self.rank[y_root]+1if __name__ == __main__:    #最多有N个用户    N=100000    result=[]    T = int(input("请输入多少组检测数据？"))    while T>0:        n = int(input("输入多少对用户关系"))        print("输入{}组用户关系".format(n))        s1=Solution(N)        for i in range(n):            cur=input()            cur_users=cur.split(" ")            s1.merge(int(cur_users[0]), int(cur_users[1]))        max_people=1        for i in range(len(s1.node_num)):            max_people=max(max_people, s1.node_num[i])        result.append(max_people)        T=T-1    for x in result:        print(x)

到此，我们的并查集就聊完了。

啰嗦一句

现在给出一个思考题，可以把你的思考写在留言区。

现在给出某个亲戚关系图，判断任意给出的两个人是否具有亲戚关系。

原创不易！各位小伙伴觉得文章不错的话，不妨点赞（在看）、留言、转发三连走起！

你知道的越多，你的思维越开阔。我们下期再见。