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

2021年11月26日 阅读数:3
这篇文章主要向大家介绍面试常考算法题之并查集问题,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

朋友圈问题

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

数据范围:1<= m <= 2 * 10 6算法

进阶:空间复杂度 O(n),时间复杂度 O(nlogn)。数组

输入描述:

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

1 ≤ T ≤ 10函数

1 ≤ n ≤ 2 * 106测试

1 ≤ x, y ≤ 105优化

输出描述:

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

示例:orm

输入:递归

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)

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

啰嗦一句

如今给出一个思考题,能够把你的思考写在留言区。

如今给出某个亲戚关系图,判断任意给出的两我的是否具备亲戚关系。

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

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