并查集 订阅
并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中,其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受;即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果,只能用并查集来描述。并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。 展开全文
并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中,其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受;即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果,只能用并查集来描述。并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。
信息
中文名
并查集
外文名
Union Find
用    途
计算机编码
并查集主要操作
初始化把每个点所在集合初始化为其自身。通常来说,这个步骤在每次使用该数据结构时只需要执行一次,无论何种实现方式,时间复杂度均为O(N)。查找查找元素所在的集合,即根节点。合并将两个元素所在的集合合并为一个集合。通常来说,合并之前,应先判断两个元素是否属于同一集合,这可用上面的“查找”操作实现。
收起全文
精华内容
参与话题
问答
  • 并查集详解 (转)

    万次阅读 多人点赞 2012-07-07 13:15:02
    并查集是我暑假从高手那里学到的一招,觉得真是太精妙的设计了。以前我无法解决的一类问题竟然可以用如此简单高效的方法搞定。不分享出来真是对不起party了。(party:我靠,关我嘛事啊?我跟你很熟么?) 来看一个...

    原文地址   :http://blog.csdn.net/niushuai666/article/details/6662911

    作者:飘过的小牛



    并查集是我暑假从高手那里学到的一招,觉得真是太精妙的设计了。以前我无法解决的一类问题竟然可以用如此简单高效的方法搞定。不分享出来真是对不起party了。(party:我靠,关我嘛事啊?我跟你很熟么?)

    来看一个实例,杭电1232畅通工程

    首先在地图上给你若干个城镇,这些城镇都可以看作点,然后告诉你哪些对城镇之间是有道路直接相连的。最后要解决的是整幅图的连通性问题。比如随意给你两个点,让你判断它们是否连通,或者问你整幅图一共有几个连通分支,也就是被分成了几个互相独立的块。像畅通工程这题,问还需要修几条路,实质就是求有几个连通分支。如果是1个连通分支,说明整幅图上的点都连起来了,不用再修路了;如果是2个连通分支,则只要再修1条路,从两个分支中各选一个点,把它们连起来,那么所有的点都是连起来的了;如果是3个连通分支,则只要再修两条路……

    以下面这组数据输入数据来说明

    4 2 1 3 4 3

    第一行告诉你,一共有4个点,2条路。下面两行告诉你,1、3之间有条路,4、3之间有条路。那么整幅图就被分成了1-3-4和2两部分。只要再加一条路,把2和其他任意一个点连起来,畅通工程就实现了,那么这个这组数据的输出结果就是1。好了,现在编程实现这个功能吧,城镇有几百个,路有不知道多少条,而且可能有回路。 这可如何是好?

    我以前也不会呀,自从用了并查集之后,嗨,效果还真好!我们全家都用它!

    并查集由一个整数型的数组和两个函数构成。数组pre[]记录了每个点的前导点是什么,函数find是查找,join是合并。

    int pre[1000 ];

    int find(int x)                                                                                                         //查找根节点

        int r=x;

        while ( pre[r ] != r )                                                                                              //返回根节点 r

              r=pre[r ];

     

        int i=x , j ;

        while( i != r )                                                                                                        //路径压缩

        {

             j = pre[ i ]; // 在改变上级之前用临时变量  j 记录下他的值 

             pre[ i ]= r ; //把上级改为根节点

             i=j;

        }

        return r ;

    }

     

     

    void join(int x,int y)                                                                                                    //判断x y是否连通,

                                                                                                 //如果已经连通,就不用管了 //如果不连通,就把它们所在的连通分支合并起,

    {

        int fx=find(x),fy=find(y);

        if(fx!=fy)

            pre[fx ]=fy;

    }

     

    为了解释并查集的原理,我将举一个更有爱的例子。 话说江湖上散落着各式各样的大侠,有上千个之多。他们没有什么正当职业,整天背着剑在外面走来走去,碰到和自己不是一路人的,就免不了要打一架。但大侠们有一个优点就是讲义气,绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”,只要是能通过朋友关系串联起来的,不管拐了多少个弯,都认为是自己人。这样一来,江湖上就形成了一个一个的群落,通过两两之间的朋友关系串联起来。而不在同一个群落的人,无论如何都无法通过朋友关系连起来,于是就可以放心往死了打。但是两个原本互不相识的人,如何判断是否属于一个朋友圈呢?

    我们可以在每个朋友圈内推举出一个比较有名望的人,作为该圈子的代表人物,这样,每个圈子就可以这样命名“齐达内朋友之队”“罗纳尔多朋友之队”……两人只要互相对一下自己的队长是不是同一个人,就可以确定敌友关系了。

    但是还有问题啊,大侠们只知道自己直接的朋友是谁,很多人压根就不认识队长,要判断自己的队长是谁,只能漫无目的的通过朋友的朋友关系问下去:“你是不是队长?你是不是队长?”这样一来,队长面子上挂不住了,而且效率太低,还有可能陷入无限循环中。于是队长下令,重新组队。队内所有人实行分等级制度,形成树状结构,我队长就是根节点,下面分别是二级队员、三级队员。每个人只要记住自己的上级是谁就行了。遇到判断敌友的时候,只要一层层向上问,直到最高层,就可以在短时间内确定队长是谁了。由于我们关心的只是两个人之间是否连通,至于他们是如何连通的,以及每个圈子内部的结构是怎样的,甚至队长是谁,并不重要。所以我们可以放任队长随意重新组队,只要不搞错敌友关系就好了。于是,门派产生了。

    http://i3.6.cn/cvbnm/6f/ec/f4/1e9cfcd3def64d26ed1a49d72c1f6db9.jpg


    下面我们来看并查集的实现。 int pre[1000]; 这个数组,记录了每个大侠的上级是谁。大侠们从1或者0开始编号(依据题意而定),pre[15]=3就表示15号大侠的上级是3号大侠。如果一个人的上级就是他自己,那说明他就是掌门人了,查找到此为止。也有孤家寡人自成一派的,比如欧阳锋,那么他的上级就是他自己。每个人都只认自己的上级。比如胡青牛同学只知道自己的上级是杨左使。张无忌是谁?不认识!要想知道自己的掌门是谁,只能一级级查上去。 find这个函数就是找掌门用的,意义再清楚不过了(路径压缩算法先不论,后面再说)。

    int find(int x)                                                                  //查找我(x)的掌门

    {

        int r=x;                                                                       //委托 r 去找掌门

        while (pre[r ]!=r)                                                        //如果r的上级不是r自己(也就是说找到的大侠他不是掌门 = =)

        r=pre[r ] ;                                                                   // r 就接着找他的上级,直到找到掌门为止。

        return  r ;                                                                   //掌门驾到~~~

    }

    再来看看join函数,就是在两个点之间连一条线,这样一来,原先它们所在的两个板块的所有点就都可以互通了。这在图上很好办,画条线就行了。但我们现在是用并查集来描述武林中的状况的,一共只有一个pre[]数组,该如何实现呢? 还是举江湖的例子,假设现在武林中的形势如图所示。虚竹小和尚与周芷若MM是我非常喜欢的两个人物,他们的终极boss分别是玄慈方丈和灭绝师太,那明显就是两个阵营了。我不希望他们互相打架,就对他俩说:“你们两位拉拉勾,做好朋友吧。”他们看在我的面子上,同意了。这一同意可非同小可,整个少林和峨眉派的人就不能打架了。这么重大的变化,可如何实现呀,要改动多少地方?其实非常简单,我对玄慈方丈说:“大师,麻烦你把你的上级改为灭绝师太吧。这样一来,两派原先的所有人员的终极boss都是师太,那还打个球啊!反正我们关心的只是连通性,门派内部的结构不要紧的。”玄慈一听肯定火大了:“我靠,凭什么是我变成她手下呀,怎么不反过来?我抗议!”抗议无效,上天安排的,最大。反正谁加入谁效果是一样的,我就随手指定了一个。这段函数的意思很明白了吧?

    void join(int x,int y)                                                                   //我想让虚竹和周芷若做朋友

    {

        int fx=find(x),fy=find(y);                                                       //虚竹的老大是玄慈,芷若MM的老大是灭绝

        if(fx!=fy)                                                                               //玄慈和灭绝显然不是同一个人

        pre[fx ]=fy;                                                                           //方丈只好委委屈屈地当了师太的手下啦

    }

    再来看看路径压缩算法。建立门派的过程是用join函数两个人两个人地连接起来的,谁当谁的手下完全随机。最后的树状结构会变成什么胎唇样,我也完全无法预计,一字长蛇阵也有可能。这样查找的效率就会比较低下。最理想的情况就是所有人的直接上级都是掌门,一共就两级结构,只要找一次就找到掌门了。哪怕不能完全做到,也最好尽量接近。这样就产生了路径压缩算法。 设想这样一个场景:两个互不相识的大侠碰面了,想知道能不能揍。 于是赶紧打电话问自己的上级:“你是不是掌门?” 上级说:“我不是呀,我的上级是谁谁谁,你问问他看看。” 一路问下去,原来两人的最终boss都是东厂曹公公。 “哎呀呀,原来是记己人,西礼西礼,在下三营六组白面葫芦娃!” “幸会幸会,在下九营十八组仙子狗尾巴花!” 两人高高兴兴地手拉手喝酒去了。 “等等等等,两位同学请留步,还有事情没完成呢!”我叫住他俩。 “哦,对了,还要做路径压缩。”两人醒悟。 白面葫芦娃打电话给他的上级六组长:“组长啊,我查过了,其习偶们的掌门是曹公公。不如偶们一起及接拜在曹公公手下吧,省得级别太低,以后查找掌门麻环。” “唔,有道理。” 白面葫芦娃接着打电话给刚才拜访过的三营长……仙子狗尾巴花也做了同样的事情。 这样,查询中所有涉及到的人物都聚集在曹公公的直接领导下。每次查询都做了优化处理,所以整个门派树的层数都会维持在比较低的水平上。路径压缩的代码,看得懂很好,看不懂也没关系,直接抄上用就行了。总之它所实现的功能就是这么个意思。

    http://i3.6.cn/cvbnm/60/98/92/745b3eac68181e4ee1fa8d1b8bca38bc.jpg


     

     

    hdu1232

    #include<iostream>
    using namespace std;
    
    int  pre[1050];
    bool t[1050];               //t 用于标记独立块的根结点
    
    int Find(int x)
    {
    	int r=x;
    	while(r!=pre[r])
    		r=pre[r];
    	
    	int i=x,j;
    	while(pre[i]!=r)
    	{
    		j=pre[i];
    		pre[i]=r;
    		i=j;
    	}
    	return r;
    }
    
    void mix(int x,int y)
    {
    	int fx=Find(x),fy=Find(y);
    	if(fx!=fy)
    	{
    		pre[fy]=fx;
    	}
    } 
    
    int main()
    {
    	int N,M,a,b,i,j,ans;
    	while(scanf("%d%d",&N,&M)&&N)
    	{
    		for(i=1;i<=N;i++)          //初始化 
    			pre[i]=i;
    		
    		for(i=1;i<=M;i++)          //吸收并整理数据 
    		{
    			scanf("%d%d",&a,&b);
    			mix(a,b);
    		}
    		
    		
    		memset(t,0,sizeof(t));
    		for(i=1;i<=N;i++)          //标记根结点
    		{
    			t[Find(i)]=1;
    		}
    		for(ans=0,i=1;i<=N;i++)
    			if(t[i])
    				ans++;
    				
    		printf("%d\n",ans-1);
    		
    	}
    	return 0;
    }//dellaserss
    


    以下为原文附的代码:

     

    回到开头提出的问题,我的代码如下:

    #include int pre[1000 ];

    int find(int x)

    {

        int r=x;

       while (pre[r ]!=r)

       r=pre[r ];

       int i=x; int j;

       while(i!=r)

       {

           j=pre[i ];

           pre[i ]=r;

           i=j;

       }

       return r;

    }

    int main()

    {

       int n,m,p1,p2,i,total,f1,f2;

       while(scanf("%d",&n) && n)         //读入n,如果n为0,结束

       {                                                    //刚开始的时候,有n个城镇,一条路都没有 //那么要修n-1条路才能把它们连起来

           total=n-1;

           //每个点互相独立,自成一个集合,从1编号到n //所以每个点的上级都是自己

           for(i=1;i<=n;i++) { pre[i ]=i; }                //共有m条路

           scanf("%d",&m); while(m--)

           { //下面这段代码,其实就是join函数,只是稍作改动以适应题目要求

               //每读入一条路,看它的端点p1,p2是否已经在一个连通分支里了

               scanf("%d %d",&p1,&p2);

               f1=find(p1);

               f2=find(p2);

                   //如果是不连通的,那么把这两个分支连起来

                   //分支的总数就减少了1,还需建的路也就减了1

               if(f1!=f2)

                {

                   pre[f2 ]=f1;

                   total--;

               }

               //如果两点已经连通了,那么这条路只是在图上增加了一个环 //对连通性没有任何影响,无视掉

           }

    //最后输出还要修的路条数

           printf("%d\n",total);

       }

       return 0;

    }

     

    展开全文
  • 并查集(Union-Find)算法介绍

    万次阅读 多人点赞 2012-06-12 13:57:16
    本文主要介绍解决动态连通性一类问题的一种算法,使用到了一种叫做并查集的数据结构,称为Union-Find。 更多的信息可以参考Algorithms 一书的Section 1.5,实际上本文也就是基于它的一篇读后感吧。 原文中更...

    本文主要介绍解决动态连通性一类问题的一种算法,使用到了一种叫做并查集的数据结构,称为Union-Find

    更多的信息可以参考Algorithms 一书的Section 1.5,实际上本文也就是基于它的一篇读后感吧。

    原文中更多的是给出一些结论,我尝试给出一些思路上的过程,即为什么要使用这个方法,而不是别的什么方法。我觉得这个可能更加有意义一些,相比于记下一些结论。


    关于动态连通性

    我们看一张图来了解一下什么是动态连通性:


    假设我们输入了一组整数对,即上图中的(4, 3) (3, 8)等等,每对整数代表这两个points/sites是连通的。那么随着数据的不断输入,整个图的连通性也会发生变化,从上图中可以很清晰的发现这一点。同时,对于已经处于连通状态的points/sites,直接忽略,比如上图中的(8, 9)


    动态连通性的应用场景:

    • 网络连接判断:

    如果每个pair中的两个整数分别代表一个网络节点,那么该pair就是用来表示这两个节点是需要连通的。那么为所有的pairs建立了动态连通图后,就能够尽可能少的减少布线的需要,因为已经连通的两个节点会被直接忽略掉。

    • 变量名等同性(类似于指针的概念)

    在程序中,可以声明多个引用来指向同一对象,这个时候就可以通过为程序中声明的引用和实际对象建立动态连通图来判断哪些引用实际上是指向同一对象。

     

    对问题建模:

    在对问题进行建模的时候,我们应该尽量想清楚需要解决的问题是什么。因为模型中选择的数据结构和算法显然会根据问题的不同而不同,就动态连通性这个场景而言,我们需要解决的问题可能是:

    • 给出两个节点,判断它们是否连通,如果连通,不需要给出具体的路径
    • 给出两个节点,判断它们是否连通,如果连通,需要给出具体的路径

     

    就上面两种问题而言,虽然只有是否能够给出具体路径的区别,但是这个区别导致了选择算法的不同,本文主要介绍的是第一种情况,即不需要给出具体路径的Union-Find算法,而第二种情况可以使用基于DFS的算法。

     

    建模思路:

    最简单而直观的假设是,对于连通的所有节点,我们可以认为它们属于一个组,因此不连通的节点必然就属于不同的组。随着Pair的输入,我们需要首先判断输入的两个节点是否连通。如何判断呢?按照上面的假设,我们可以通过判断它们属于的组,然后看看这两个组是否相同,如果相同,那么这两个节点连通,反之不连通。为简单起见,我们将所有的节点以整数表示,即对N个节点使用0N-1的整数表示。而在处理输入的Pair之前,每个节点必然都是孤立的,即他们分属于不同的组,可以使用数组来表示这一层关系,数组的index是节点的整数表示,而相应的值就是该节点的组号了。该数组可以初始化为:

    for(int i = 0; i < size; i++)
    	id[i] = i;  
    


    即对于节点i,它的组号也是i

     

    初始化完毕之后,对该动态连通图有几种可能的操作:

    • 查询节点属于的组

    数组对应位置的值即为组号

    • 判断两个节点是否属于同一个组

    分别得到两个节点的组号,然后判断组号是否相等

    • 连接两个节点,使之属于同一个组

    分别得到两个节点的组号,组号相同时操作结束,不同时,将其中的一个节点的组号换成另一个节点的组号

    • 获取组的数目

    初始化为节点的数目,然后每次成功连接两个节点之后,递减1


    API

    我们可以设计相应的API




    注意其中使用整数来表示节点,如果需要使用其他的数据类型表示节点,比如使用字符串,那么可以用哈希表来进行映射,即将String映射成这里需要的Integer类型。

     

    分析以上的API,方法connectedunion都依赖于findconnected对两个参数调用两次find方法,而union在真正执行union之前也需要判断是否连通,这又是两次调用find方法。因此我们需要把find方法的实现设计的尽可能的高效。所以就有了下面的Quick-Find实现。


    Quick-Find 算法:

    public class UF
    {
    	private int[] id; // access to component id (site indexed)
    	private int count; // number of components
    	public UF(int N)
    	{
    		// Initialize component id array.
    		count = N;
    		id = new int[N];
    		for (int i = 0; i < N; i++)
    			id[i] = i;
    	}
    	public int count()
    	{ return count; }
    	public boolean connected(int p, int q)
    	{ return find(p) == find(q); }
    	public int find(int p)
    	{ return id[p]; }
    	public void union(int p, int q)
    	{ 
    		// 获得p和q的组号
    		int pID = find(p);
    		int qID = find(q);
    		// 如果两个组号相等,直接返回
    		if (pID == qID) return;
    		// 遍历一次,改变组号使他们属于一个组
    		for (int i = 0; i < id.length; i++)
    			if (id[i] == pID) id[i] = qID;
    		count--;
    	}
    }
    

    举个例子,比如输入的Pair(5 9),那么首先通过find方法发现它们的组号并不相同,然后在union的时候通过一次遍历,将组号1都改成8。当然,由8改成1也是可以的,保证操作时都使用一种规则就行。



    上述代码的find方法十分高效,因为仅仅需要一次数组读取操作就能够找到该节点的组号,但是问题随之而来,对于需要添加新路径的情况,就涉及到对于组号的修改,因为并不能确定哪些节点的组号需要被修改,因此就必须对整个数组进行遍历,找到需要修改的节点,逐一修改,这一下每次添加新路径带来的复杂度就是线性关系了,如果要添加的新路径的数量是M,节点数量是N,那么最后的时间复杂度就是MN,显然是一个平方阶的复杂度,对于大规模的数据而言,平方阶的算法是存在问题的,这种情况下,每次添加新路径就是“牵一发而动全身”,想要解决这个问题,关键就是要提高union方法的效率,让它不再需要遍历整个数组。

     

    Quick-Union 算法:

    考虑一下,为什么以上的解法会造成“牵一发而动全身”?因为每个节点所属的组号都是单独记录,各自为政的,没有将它们以更好的方式组织起来,当涉及到修改的时候,除了逐一通知、修改,别无他法。所以现在的问题就变成了,如何将节点以更好的方式组织起来,组织的方式有很多种,但是最直观的还是将组号相同的节点组织在一起,想想所学的数据结构,什么样子的数据结构能够将一些节点给组织起来?常见的就是链表,图,树,什么的了。但是哪种结构对于查找和修改的效率最高?毫无疑问是树,因此考虑如何将节点和组的关系以树的形式表现出来。

     

    如果不改变底层数据结构,即不改变使用数组的表示方法的话。可以采用parent-link的方式将节点组织起来,举例而言,id[p]的值就是p节点的父节点的序号,如果p是树根的话,id[p]的值就是p,因此最后经过若干次查找,一个节点总是能够找到它的根节点,即满足id[root] = root的节点也就是组的根节点了,然后就可以使用根节点的序号来表示组号。所以在处理一个pair的时候,将首先找到pair中每一个节点的组号(即它们所在树的根节点的序号),如果属于不同的组的话,就将其中一个根节点的父节点设置为另外一个根节点,相当于将一颗独立的树编程另一颗独立的树的子树。直观的过程如下图所示。但是这个时候又引入了问题。



    在实现上,和之前的Quick-Find只有findunion两个方法有所不同:

    private int find(int p)
    { 
    	// 寻找p节点所在组的根节点,根节点具有性质id[root] = root
    	while (p != id[p]) p = id[p];
    	return p;
    }
    public void union(int p, int q)
    { 
    	// Give p and q the same root.
    	int pRoot = find(p);
    	int qRoot = find(q);
    	if (pRoot == qRoot) 
    		return;
    	id[pRoot] = qRoot;    // 将一颗树(即一个组)变成另外一课树(即一个组)的子树
    	count--;
    }
    

    树这种数据结构容易出现极端情况,因为在建树的过程中,树的最终形态严重依赖于输入数据本身的性质,比如数据是否排序,是否随机分布等等。比如在输入数据是有序的情况下,构造的BST会退化成一个链表。在我们这个问题中,也是会出现的极端情况的,如下图所示。



    为了克服这个问题,BST可以演变成为红黑树或者AVL树等等。

     

    然而,在我们考虑的这个应用场景中,每对节点之间是不具备可比性的。因此需要想其它的办法。在没有什么思路的时候,多看看相应的代码可能会有一些启发,考虑一下Quick-Union算法中的union方法实现:

    public void union(int p, int q)
    { 
    	// Give p and q the same root.
    	int pRoot = find(p);
    	int qRoot = find(q);
    	if (pRoot == qRoot) 
    		return;
    	id[pRoot] = qRoot;  // 将一颗树(即一个组)变成另外一课树(即一个组)的子树
    	count--;
    }
    

    上面 id[pRoot] = qRoot 这行代码看上去似乎不太对劲。因为这也属于一种“硬编码”,这样实现是基于一个约定,即p所在的树总是会被作为q所在树的子树,从而实现两颗独立的树的融合。那么这样的约定是不是总是合理的呢?显然不是,比如p所在的树的规模比q所在的树的规模大的多时,pq结合之后形成的树就是十分不和谐的一头轻一头重的”畸形树“了。


    所以我们应该考虑树的大小,然后再来决定到底是调用:

    id[pRoot] = qRoot 或者是 id[qRoot] = pRoot



    即总是size小的树作为子树和size大的树进行合并。这样就能够尽量的保持整棵树的平衡。

     

    所以现在的问题就变成了:树的大小该如何确定?

    我们回到最初的情形,即每个节点最一开始都是属于一个独立的组,通过下面的代码进行初始化:

    for (int i = 0; i < N; i++)
    	id[i] = i;    // 每个节点的组号就是该节点的序号
    


    以此类推,在初始情况下,每个组的大小都是1,因为只含有一个节点,所以我们可以使用额外的一个数组来维护每个组的大小,对该数组的初始化也很直观:

    for (int i = 0; i < N; i++)
    	sz[i] = 1;    // 初始情况下,每个组的大小都是1
    


    而在进行合并的时候,会首先判断待合并的两棵树的大小,然后按照上面图中的思想进行合并,实现代码:

    public void union(int p, int q)
    {
    	int i = find(p);
    	int j = find(q);
    	if (i == j) return;
    	// 将小树作为大树的子树
    	if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; }
    	else { id[j] = i; sz[i] += sz[j]; }
    	count--;
    }
    

    Quick-Union  Weighted Quick-Union 的比较:



    可以发现,通过sz数组决定如何对两棵树进行合并之后,最后得到的树的高度大幅度减小了。这是十分有意义的,因为在Quick-Union算法中的任何操作,都不可避免的需要调用find方法,而该方法的执行效率依赖于树的高度。树的高度减小了,find方法的效率就增加了,从而也就增加了整个Quick-Union算法的效率。

     

    上图其实还可以给我们一些启示,即对于Quick-Union算法而言,节点组织的理想情况应该是一颗十分扁平的树,所有的孩子节点应该都在height1的地方,即所有的孩子都直接连接到根节点。这样的组织结构能够保证find操作的最高效率。

     

    那么如何构造这种理想结构呢?

    find方法的执行过程中,不是需要进行一个while循环找到根节点嘛?如果保存所有路过的中间节点到一个数组中,然后在while循环结束之后,将这些中间节点的父节点指向根节点,不就行了么?但是这个方法也有问题,因为find操作的频繁性,会造成频繁生成中间节点数组,相应的分配销毁的时间自然就上升了。那么有没有更好的方法呢?还是有的,即将节点的父节点指向该节点的爷爷节点,这一点很巧妙,十分方便且有效,相当于在寻找根节点的同时,对路径进行了压缩,使整个树结构扁平化。相应的实现如下,实际上只需要添加一行代码:

    private int find(int p)
    {
    	while (p != id[p])
    	{
    		// 将p节点的父节点设置为它的爷爷节点
    		id[p] = id[id[p]];
    		p = id[p];
    	}
    	return p;
    }
    

    至此,动态连通性相关的Union-Find算法基本上就介绍完了,从容易想到的Quick-Find到相对复杂但是更加高效的Quick-Union,然后到对Quick-Union的几项改进,让我们的算法的效率不断的提高。

    这几种算法的时间复杂度如下所示:

    Algorithm

    Constructor

    Union

    Find

    Quick-Find

    N

    N

    1

    Quick-Union

    N

    Tree height

    Tree height

    Weighted Quick-Union

    N

    lgN

    lgN

    Weighted Quick-Union With Path Compression

    N

    Very near to 1 (amortized)

    Very near to 1 (amortized)

     

    对大规模数据进行处理,使用平方阶的算法是不合适的,比如简单直观的Quick-Find算法,通过发现问题的更多特点,找到合适的数据结构,然后有针对性的进行改进,得到了Quick-Union算法及其多种改进算法,最终使得算法的复杂度降低到了近乎线性复杂度。

     

    如果需要的功能不仅仅是检测两个节点是否连通,还需要在连通时得到具体的路径,那么就需要用到别的算法了,比如DFS或者BFS。


    并查集的应用,可以参考另外一篇文章 并查集应用举例




    展开全文
  • 并查集详解 ——图文解说,简单易懂(转)

    万次阅读 多人点赞 2016-03-10 17:38:08
    并查集是我暑假从高手那里学到的一招,觉得真是太精妙的设计了。以前我无法解决的一类问题竟然可以用如此简单高效的方法搞定。不分享出来真是对不起party了。(party:我靠,关我嘛事啊?我跟你很熟么?) 来看一个...

    并查集是我暑假从高手那里学到的一招,觉得真是太精妙的设计了。以前我无法解决的一类问题竟然可以用如此简单高效的方法搞定。不分享出来真是对不起party了。(party:我靠,关我嘛事啊?我跟你很熟么?)

    来看一个实例,HDU1232畅通工程

    首先在地图上给你若干个城镇,这些城镇都可以看作点,然后告诉你哪些对城镇之间是有道路直接相连的。最后要解决的是整幅图的连通性问题。比如随意给你两个点,让你判断它们是否连通,或者问你整幅图一共有几个连通分支,也就是被分成了几个互相独立的块。像畅通工程这题,问还需要修几条路,实质就是求有几个连通分支。如果是1个连通分支,说明整幅图上的点都连起来了,不用再修路了;如果是2个连通分支,则只要再修1条路,从两个分支中各选一个点,把它们连起来,那么所有的点都是连起来的了;如果是3个连通分支,则只要再修两条路……

    以下面这组数据输入数据来说明

    4 2 1 3 4 3

    第一行告诉你,一共有4个点,2条路。下面两行告诉你,1、3之间有条路,4、3之间有条路。那么整幅图就被分成了1-3-4和2两部分。只要再加一条路,把2和其他任意一个点连起来,畅通工程就实现了,那么这个这组数据的输出结果就是1。好了,现在编程实现这个功能吧,城镇有几百个,路有不知道多少条,而且可能有回路。 这可如何是好?

    我以前也不会呀,自从用了并查集之后,嗨,效果还真好!我们全家都用它!

    并查集由一个整数型的数组和两个函数构成。数组pre[]记录了每个点的前导点是什么,函数find是查找,join是合并。

    int pre[1000 ];
    int find(int x)                                       //查找根节点
    { 
        int r=x;
        while ( pre[r] != r )                           //返回根节点 r
              r=pre[r];
     
        int i=x , j ;
        while( i != r )                                   //路径压缩
        {
             j = pre[ i ]; 				// 在改变上级之前用临时变量  j 记录下他的值 
             pre[ i ]= r ; 				//把上级改为根节点
             i=j;
        }
        return r ;
    }
     

    void join(int x,int y)                           //判断x y是否连通,
                                                   //如果已经连通,就不用管了 如果不连通,就把它们所在的连通分支合并起,
    {
        int fx=find(x),fy=find(y);
        if(fx!=fy)
            pre[fx ]=fy;
    }


     

    为了解释并查集的原理,我将举一个更有爱的例子。 话说江湖上散落着各式各样的大侠,有上千个之多。他们没有什么正当职业,整天背着剑在外面走来走去,碰到和自己不是一路人的,就免不了要打一架。但大侠们有一个优点就是讲义气,绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”,只要是能通过朋友关系串联起来的,不管拐了多少个弯,都认为是自己人。这样一来,江湖上就形成了一个一个的群落,通过两两之间的朋友关系串联起来。而不在同一个群落的人,无论如何都无法通过朋友关系连起来,于是就可以放心往死了打。但是两个原本互不相识的人,如何判断是否属于一个朋友圈呢?

    我们可以在每个朋友圈内推举出一个比较有名望的人,作为该圈子的代表人物,这样,每个圈子就可以这样命名“齐达内朋友之队”“罗纳尔多朋友之队”……两人只要互相对一下自己的队长是不是同一个人,就可以确定敌友关系了。

    但是还有问题啊,大侠们只知道自己直接的朋友是谁,很多人压根就不认识队长,要判断自己的队长是谁,只能漫无目的的通过朋友的朋友关系问下去:“你是不是队长?你是不是队长?”这样一来,队长面子上挂不住了,而且效率太低,还有可能陷入无限循环中。于是队长下令,重新组队。队内所有人实行分等级制度,形成树状结构,我队长就是根节点,下面分别是二级队员、三级队员。每个人只要记住自己的上级是谁就行了。遇到判断敌友的时候,只要一层层向上问,直到最高层,就可以在短时间内确定队长是谁了。由于我们关心的只是两个人之间是否连通,至于他们是如何连通的,以及每个圈子内部的结构是怎样的,甚至队长是谁,并不重要。所以我们可以放任队长随意重新组队,只要不搞错敌友关系就好了。于是,门派产生了。

    下面我们来看并查集的实现。 int pre[1000]; 这个数组,记录了每个大侠的上级是谁。大侠们从1或者0开始编号(依据题意而定),pre[15]=3就表示15号大侠的上级是3号大侠。如果一个人的上级就是他自己,那说明他就是掌门人了,查找到此为止。也有孤家寡人自成一派的,比如欧阳锋,那么他的上级就是他自己。每个人都只认自己的上级。比如胡青牛同学只知道自己的上级是杨左使。张无忌是谁?不认识!要想知道自己的掌门是谁,只能一级级查上去。 find这个函数就是找掌门用的,意义再清楚不过了(路径压缩算法先不论,后面再说)。

    int find(int x)                    //查找我(x)的掌门
    {
        int r=x;                      //委托 r 去找掌门
        while (pre[r ]!=r)           //如果r的上级不是r自己(也就是说找到的大侠他不是掌门 = =)
        r=pre[r ] ;                 // r 就接着找他的上级,直到找到掌门为止。
        return  r ;                //掌门驾到~~~
    }


    再来看看join函数,就是在两个点之间连一条线,这样一来,原先它们所在的两个板块的所有点就都可以互通了。这在图上很好办,画条线就行了。但我们现在是用并查集来描述武林中的状况的,一共只有一个pre[]数组,该如何实现呢? 还是举江湖的例子,假设现在武林中的形势如图所示。虚竹小和尚与周芷若MM是我非常喜欢的两个人物,他们的终极boss分别是玄慈方丈和灭绝师太,那明显就是两个阵营了。我不希望他们互相打架,就对他俩说:“你们两位拉拉勾,做好朋友吧。”他们看在我的面子上,同意了。这一同意可非同小可,整个少林和峨眉派的人就不能打架了。这么重大的变化,可如何实现呀,要改动多少地方?其实非常简单,我对玄慈方丈说:“大师,麻烦你把你的上级改为灭绝师太吧。这样一来,两派原先的所有人员的终极boss都是师太,那还打个球啊!反正我们关心的只是连通性,门派内部的结构不要紧的。”玄慈一听肯定火大了:“我靠,凭什么是我变成她手下呀,怎么不反过来?我抗议!”抗议无效,上天安排的,最大。反正谁加入谁效果是一样的,我就随手指定了一个。这段函数的意思很明白了吧?

    void join(int x,int y)          //我想让虚竹和周芷若做朋友
    {
        int fx=find(x),fy=find(y);         //虚竹的老大是玄慈,芷若MM的老大是灭绝
        if(fx!=fy)                         //玄慈和灭绝显然不是同一个人
        pre[fx ]=fy;                       //方丈只好委委屈屈地当了师太的手下啦
    }


    再来看看路径压缩算法。建立门派的过程是用join函数两个人两个人地连接起来的,谁当谁的手下完全随机。最后的树状结构会变成什么胎唇样,我也完全无法预计,一字长蛇阵也有可能。这样查找的效率就会比较低下。最理想的情况就是所有人的直接上级都是掌门,一共就两级结构,只要找一次就找到掌门了。哪怕不能完全做到,也最好尽量接近。这样就产生了路径压缩算法。 设想这样一个场景:两个互不相识的大侠碰面了,想知道能不能揍。 于是赶紧打电话问自己的上级:“你是不是掌门?” 上级说:“我不是呀,我的上级是谁谁谁,你问问他看看。” 一路问下去,原来两人的最终boss都是东厂曹公公。 “哎呀呀,原来是记己人,西礼西礼,在下三营六组白面葫芦娃!” “幸会幸会,在下九营十八组仙子狗尾巴花!” 两人高高兴兴地手拉手喝酒去了。 “等等等等,两位同学请留步,还有事情没完成呢!”我叫住他俩。 “哦,对了,还要做路径压缩。”两人醒悟。 白面葫芦娃打电话给他的上级六组长:“组长啊,我查过了,其习偶们的掌门是曹公公。不如偶们一起及接拜在曹公公手下吧,省得级别太低,以后查找掌门麻环。” “唔,有道理。” 白面葫芦娃接着打电话给刚才拜访过的三营长……仙子狗尾巴花也做了同样的事情。 这样,查询中所有涉及到的人物都聚集在曹公公的直接领导下。每次查询都做了优化处理,所以整个门派树的层数都会维持在比较低的水平上。路径压缩的代码,看得懂很好,看不懂也没关系,直接抄上用就行了。总之它所实现的功能就是这么个意思。


    展开全文
  • 并查集

    千次阅读 多人点赞 2016-05-16 17:58:33
    并查集(Union-find Sets)是一种非常精巧而实用的数据结构,它主要用于处理一些不相交集合的合并问题。一些常见的用途有求连通子图、求最小生成树的 Kruskal 算法和求最近公共祖先(Least Common Ancestors, LCA)...

    一.基本概念和定义

    并查集(Union-find Sets)是一种非常精巧而实用的数据结构,它主要用于处理一些不相交集合的合并问题。一些常见的用途有求连通子图、求最小生成树的 Kruskal 算法和求最近公共祖先(Least Common Ancestors, LCA)等。

    使用并查集时,首先会存在一组不相交的动态集合 S={S1,S2,,Sk}S={S1,S2,⋯,Sk},一般都会使用一个整数表示集合中的一个元素。

    每个集合可能包含一个或多个元素,并选出集合中的某个元素作为代表。每个集合中具体包含了哪些元素是不关心的,具体选择哪个元素作为代表一般也是不关心的。我们关心的是,对于给定的元素,可以很快的找到这个元素所在的集合(的代表),以及合并两个元素所在的集合,而且这些操作的时间复杂度都是常数级的。

    并查集的基本操作有三个:

    1. intit():初始化一个新的并查集,其中包含 s 个单元素集合。
    2. merge(x, y):把元素 x 和元素 y 所在的集合合并,要求 x 和 y 所在的集合不相交,如果相交则不合并。
    3. find(x):找到元素 x 所在的集合的代表,该操作也可以用于判断两个元素是否位于同一个集合,只要将它们各自的代表比较一下就可以了。
    二.原理解释

    相信大家每次在搜索资料查询并查集的时候总是邹巴巴的文字,甚至连图片都没有。
    下面,掀起江湖的腥风血雨来趣味解释并查集的原理

     话说江湖上散落着各式各样的大侠,有上千个之多。他们没有什么正当职业,整天背着剑在外面走来走去,碰到和自己不是一路人的,就免不了要打一架。但大侠们有一个优点就是讲义气,绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”,只要是能通过朋友关系串联起来的,不管拐了多少个弯,都认为是自己人。这样一来,江湖上就形成了一个一个的群落,通过两两之间的朋友关系串联起来。而不在同一个群落的人,无论如何都无法通过朋友关系连起来,于是就可以放心往死了打。但是两个原本互不相识的人,如何判断是否属于一个朋友圈呢?我们可以在每个朋友圈内推举出一个比较有名望的人,作为该圈子的代表人物,这样,每个圈子就可以这样命名“齐达内朋友之队”“罗纳尔多朋友之队”……两人只要互相对一下自己的队长是不是同一个人,就可以确定敌友关系了。
         但是还有问题啊,大侠们只知道自己直接的朋友是谁,很多人压根就不认识队长,要判断自己的队长是谁,只能漫无目的的通过朋友的朋友关系问下去:“你是不是队长?你是不是队长?”这样一来,队长面子上挂不住了,而且效率太低,还有可能陷入无限循环中。于是队长下令,重新组队。队内所有人实行分等级制度,形成树状结构,我队长就是根节点,下面分别是二级队员、三级队员。每个人只要记住自己的上级是谁就行了。遇到判断敌友的时候,只要一层层向上问,直到最高层,就可以在短时间内确定队长是谁了。由于我们关心的只是两个人之间是否连通,至于他们是如何连通的,以及每个圈子内部的结构是怎样的,甚至队长是谁,并不重要。所以我们可以放任队长随意重新组队,只要不搞错敌友关系就好了。于是,门派产生了。

    下面我们来看并查集的实现。

    各个门派掌门在成立各派之前,还是孤家寡人的时候,每个元素都是一个单元素集合,即父节点是其自身:

    int pre[1000];
         这个数组,记录了每个大侠的上级是谁。大侠们从1或者0开始编号(依据题意而定),pre[15]=3就表示15号大侠的上级是3号大侠。如果一个人的上级就是他自己,那说明他就是掌门人了,查找到此为止。也有孤家寡人自成一派的,比如欧阳锋,那么他的上级就是他自己。每个人都只认自己的上级。比如胡青牛同学只知道自己的上级是杨左使。张无忌是谁?不认识!要想知道自己的掌门是谁,只能一级级查上去。

    void init(){
    	//for(int i=0;i<size;i++)pre[i]=i;//父节点是其本身
    	memset(pre,-1,sizeof(pre))//这里用到了一个小技巧,即:掌门人的父结点是一个负数,且这个负数的绝对值表示的是当前门派人数;
    }


    接下来,就是 find 操作了,如果每次都沿着父节点向上查找,那时间复杂度就是树的高度,完全不可能达到常数级。这里需要应用一种非常简单而有效的策略——路径压缩。

    再来看看路径压缩算法。建立门派的过程是用join函数两个人两个人地连接起来的,谁当谁的手下完全随机。最后的树状结构会变成什么胎唇样,我也完全无法预计,一字长蛇阵也有可能。这样查找的效率就会比较低下。最理想的情况就是所有人的直接上级都是掌门,一共就两级结构,只要找一次就找到掌门了。哪怕不能完全做到,也最好尽量接近。这样就产生了路径压缩算法。
         设想这样一个场景:两个互不相识的大侠碰面了,想知道能不能揍。
         于是赶紧打电话问自己的上级:“你是不是掌门?”
         上级说:“我不是呀,我的上级是谁谁谁,你问问他看看。”
         一路问下去,原来两人的最终boss都是东厂曹公公。
    “哎呀呀,原来是记己人,西礼西礼,在下三营六组白面葫芦娃!”
    “幸会幸会,在下九营十八组仙子狗尾巴花!”
         两人高高兴兴地手拉手喝酒去了。
         “等等等等,两位同学请留步,还有事情没完成呢!”我叫住他俩。
         “哦,对了,还要做路径压缩。”两人醒悟。
         白面葫芦娃打电话给他的上级六组长:“组长啊,我查过了,其习偶们的掌门是曹公公。不如偶们一起及接拜在曹公公手下吧,省得级别太低,以后查找掌门麻环。”
         “唔,有道理。”
         白面葫芦娃接着打电话给刚才拜访过的三营长……仙子狗尾巴花也做了同样的事情。
         这样,查询中所有涉及到的人物都聚集在曹公公的直接领导下。每次查询都做了优化处理,所以整个门派树的层数都会维持在比较低的水平上。路径压缩的代码所实现的功能就是这么个意思。



         find这个函数就是找掌门用的.

    int find(int x){
    	//return pre[x] == x ? x : find(pre[x]);
    	return pre[x] < 0 ? x : find(pre[x]);
    }

    再来看看merge函数,就是在两个点之间连一条线,这样一来,原先它们所在的两个板块的所有点就都可以互通了。这在图上很好办,画条线就行了。但我们现在是用并查集来描述武林中的状况的,一共只有一个pre[]数组,该如何实现呢?
         还是举江湖的例子,假设现在武林中的形势如图所示。虚竹小和尚与周芷若MM是我非常喜欢的两个人物,他们的终极boss分别是玄慈方丈和灭绝师太,那明显就是两个阵营了。我不希望他们互相打架,就对他俩说:“你们两位拉拉勾,做好朋友吧。”他们看在我的面子上,同意了。这一同意可非同小可,整个少林和峨眉派的人就不能打架了。这么重大的变化,可如何实现呀,要改动多少地方?其实非常简单,我对玄慈方丈说:“大师,麻烦你把你的上级改为灭绝师太吧。这样一来,两派原先的所有人员的终极boss都是师太,那还打个球啊!反正我们关心的只是连通性,门派内部的结构不要紧的。”玄慈一听肯定火大了:“我靠,凭什么是我变成她手下呀,怎么不反过来?我抗议!”抗议无效,上天安排的,最大。反正谁加入谁效果是一样的,我就随手指定了一个。

    void merge(int x, int y)//虚竹和周芷若做朋友 
    {
    	int fx = find(x), f[y] = find(y);//一个老大是玄慈,一个是灭绝师太
    	if (fx != fy)//不是同一个人
    	{
    		pre[fy] += pre[fx];//归顺以后原先是两个门派的成员变为一个门派,人数自然是两个门派之和
    		pre[fx] = fy;//方丈很委屈的做了灭绝的小弟 //选定一个原则,如果是靠左原则,则将所有左边的归顺右边,反之亦然。
    	}
    		
    }





    贴一个完整代码:这个程序用于统计n个人,m个两两关系的门派的个数以及每一个门派的人员数量。

    代码很简单。也很容易理解

    #include<iostream>
    #include<cstring>
    using namespace std;
    int n, m;//n个人,m个两两团伙,团伙之间存在传递性,即A<->B,B<->C那么A.B.C均是同一门派。 
    
    int pre[1000];//用来找掌门用的 
    int ans;//门派的数量; 
    void init()
    {
    	memset(pre, -1, sizeof(pre));
    }
    
    int find(int x)//有路径压缩版 
    {
    	if (pre[x]<0)return x;
    	return find(pre[x]);
    }
    
    void merge(int x, int y)//虚竹和周芷若做朋友 
    {
    	int fx = find(x);
    	int fy = find(y);//一个老大是玄慈,一个是灭绝师太
    
    	if (fx != fy)//不是同一个人
    	{
    		pre[fy] += pre[fx];
    		pre[fx] = fy;//方丈很委屈的做了灭绝的小弟 ,靠右原则;
    	}
    		 
    }
    
    int main()
    {
    	while (cin >> n >> m)
    	{
    		ans = 0;
    		init();
    
    		for (int i = 0; i<m; i++)
    		{
    			int x, y;
    			cin >> x >> y;
    			merge(x, y);
    		}
    
    		for (int i = 0; i<n; i++)
    		{
    			if (pre[i]<0)
    			{
    				ans++;
    				//输出每一门派的人员数量 
    				cout << -pre[i] << endl;
    			}
    
    		}
    
    		//输出所有门派的数量; 
    		cout << ans << endl;
    	}
    
    
    	return 0;
    }
    
    


    展开全文
  • 并查集Java代码模板

    2020-11-12 23:03:15
    并查集 1.什么是并查集 并查集是一种树型的数据结构,用于处理一些不交集的合并及查询问题。它可以支持两种操作 (1) 将两个不相交的集合合并 (2) 判断两个元素是否在一个集合中 两种操作的时间复杂度近乎O(1)O(1)O(1...
  • 并查集问题

    2020-04-01 20:09:01
    并查集 并查集是一种树型的数据结构,用于处理一些不交集的合并及查询问题。 这里面主要就两种操作: 1、查询find()函数:就是一种递归查找,需要找x的根,就不断寻找x的父亲,直到找到那个根。 int find(int x) { ...
  • 并查集算法介绍

    千次阅读 2015-08-09 18:57:58
    我们在一些应用当中,经常会遇到将n个不同的元素分成一组不相交的集合,例如某省调查城镇交通状况,得到现有城镇道路...这里,我们介绍如何维护一种被称为“并查集”的数据结构来实现这些操作。 在此文中,我们综合了网
  • 并查集算法

    2020-03-19 20:00:33
    并查集操作、原理、代码实现、例题
  • 并查集算法总结

    千次阅读 2018-08-08 17:14:49
    并查集可以称之为不相交集合,在...并查集是一种非常精巧而实用的数据结构,主要用于处理一些不相交集合的合并问题,一些常见的用途有求连通子图、最小生成树的karkal算法、和求最近共同祖先等问题。 使用并查集时...
  • 并查集算法应用

    2020-01-02 20:11:47
    并查集概念 并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。 并查集也被称为不相交集数据结构。顾名思义,并查集主要操作是合并与查询,它是...
  • c++ 写并查集算法模板

    2019-03-17 20:23:54
    给出一个有向图,经过并查集算法可以很快地判断任意连个点是否属于同一个集合。 #include&lt;iostream&gt; #include&lt;stdio.h&gt; #include&lt;string.h&gt; #define MAXN 1000 using ...
  • 并查集算法 C语言

    千次阅读 2020-01-23 21:57:01
    算法》中的讲解,自己理解了一下并查集的内容,感觉,这是个超级有趣超级简单容易理解的算法知识。 例题 -下面通过一个题目详细说明一下: 有n个人,编号1-n。现在有一个舞会,在舞会上,大家会相互介绍自己的朋友。...
  • 本人是小白,在解题的时候发现并查集非常有用,在网上查找有关资料,发现其中一篇非常好,故作分享 链接http:点击打开链接
  • JAVA并查集算法

    2020-03-09 16:12:52
    https://blog.csdn.net/qq_42011541/article/details/83378709
  • java实现并查集算法

    千次阅读 2017-07-13 21:43:31
    并查集 并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。集就是让每个元素构成一个单元素的集合,也就是按一定顺序将属于同一组的元素所在的集合...
  • STL——并查集算法

    2019-01-23 11:12:27
    并查集可以称之为不相交集合,在...并查集是一种非常精巧而实用的数据结构,主要用于处理一些不相交集合的合并问题,一些常见的用途有求连通子图、最小生成树的karkal算法、和求最近共同祖先等问题。 使用并查集时...
  • 并查集的概念 并查集的操作 并查集的实现和优化 Quick Find Quick Union 基于size的优化 基于rank的优化 路径压缩优化 并查集的时间复杂度 并查集的概念 在计算机科学中,并查集 是一种树形的数据结构,用于...
  • 并查集算法----犯罪团伙(黑科技)

    千次阅读 2016-10-14 13:41:45
    一、题目描述 犯罪团伙(gang.cpp) 题目描述  警察抓到了n个罪犯,警察根据经验知道他们属于不同的犯罪团伙,却不能判断有多少个团伙,但通过警察的审讯,知道其中的一些罪犯之间相互认识,已知同一犯罪团伙的成员...
  • 并查集算法和路径压缩

    千次阅读 2016-04-11 17:34:07
    并查集是我暑假从高手那里学到的一招,觉得真是太精妙的设计了。以前我无法解决的一类问题竟然可以用如此简单高效的方法搞定。不分享出来真是对不起party了。(party:我靠,关我嘛事啊?我跟你很熟么?) 来看一个...
  • 并查集算法真的是简单却又非常实用的一种算法,要想理解这个算法可以用一个非常生动的例子说明,叫解密犯罪团伙,这是从《啊哈算法》看到的,讲解的非常生动形象。在一堆数量为n的犯人里,如果n1和n2是团伙,n2又和...
  • 小谈并查集及其算法实现

    千次阅读 2015-08-21 14:49:36
    并查集   一、算法介绍: 并查集(Union-find Sets)是一种非常精巧而实用的数据结构,它主要用于处理一些不相交集合的合并问题。   并查集的基本操作有两个: 1:合并 union(x, y):把元素 x 和元素 y 所在...
  • 并查集的理解与实现总结

    千次阅读 多人点赞 2017-11-25 17:44:47
    并查集的应用十分广泛,包括一些算法,当应用上并查集的时候,也会更容易实现。下面总结下并查集的相关内容。 什么是并查集? 个人的理解是:并查集就是对集合三种常用操作的再一次抽象。分别是集合的合并(Union...
  • Java实现并查集

    千次阅读 多人点赞 2018-10-25 14:08:14
    这次需要介绍的就是并查集 并查集的简单应用就是连通图—网络通信连接 等等 总之很重要 那么先说一下 这次的算法是 1. union-find (简单并查集) 2.quick-union (优化的并查集) 3.加权值quick-union(处理了2...
  • 最近通过python的numba库进行实现了并查集的运算,但是只跑通了blockspergrid=1,threadsperblock=1的形式,速度比cpu还慢,我对cuda加速不太懂,想问问这块是否能真的加速
  • 并查集(Union-Find)算法详解

    万次阅读 多人点赞 2017-12-08 16:15:05
    并查集(Union-Find)是解决动态连通性问题的一类非常高效的数据结构。本文中,我将尽我所能用最简单,最清晰的逻辑展示出并查集的构造过程,同时还将对其中的关键步骤给出相应的Python代码。动态连通性可以想象一张...
  • c++并查集基础

    千次阅读 多人点赞 2018-06-09 17:21:56
    并查集 是一种树型的数据结构,用于处理一些不相加集合的合并和查询问题。在使用中常常以森林来表示。 并查集也是用来维护集合的,和前面学习的set不同之处在于,并查集能很方便地同时维护很多集合。如果用set来维护会...
  • 并查集算法模板

    2016-09-20 09:13:04
    并查集 int findx(int x) {  return bin[x]==x?x:findx(bin[x]);//查找根节点,判断是否在同一个集合 } void join(int a, int b)//合并两个点 {  int x, y;    x = findx(a);  y = findx(b);    if
  • 并查集算法进阶学习

    千次阅读 2014-07-11 14:54:13
    继续数据结构的复习,本次的专题是:并查集。  并查集,顾名思义,干的就是“并”和“查”两件事。很多与集合相关的操作都可以用并查集高效的解决。  两个操作代码:  int Find(int x)  {  if (tree[x...

空空如也

1 2 3 4 5 ... 20
收藏数 619,103
精华内容 247,641
关键字:

并查集