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

2021/11/26 1:10:17

本文主要是介绍面试常考算法题之并查集问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

朋友圈问题

现在有 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

输出描述:

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

示例:

输入:

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)

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

啰嗦一句

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

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

原创不易!各位小伙伴觉得文章不错的话,不妨点赞(在看)、留言、转发三连走起!

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



这篇关于面试常考算法题之并查集问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程