腾讯校招朋友圈问题

并查集问题

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

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

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

输入描述:

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

输出描述:

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

示例：

输入：

2
4
1 2
3 4
5 6
1 6
4
1 2
3 4
5 6
7 8

输出：

4
2

分析问题

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

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

首先，我们来看一下什么是并查集。并查集是用来求解一些元素分组的问题，即将一系列的元素分组到不想交的集合中，并支持合并和查询操作。

• 合并（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]+1


if __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)

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