并查集的简介

关键词：

　　最近做题用到了并查集索性就把自己所掌握的相关知识总结一下。

　　并查集(union-find sets),CLRS上称为disjoint-set,是一组不相交的动态集合S1,S2,....Sk。它能够实现较快的合并和判断元素所在集合的操作，应用比较广泛，如其求无向图的连通分量个数，利用Kruskar算法求最小生成树等。它的主要操作为分为三部分：

1.初始化集合,Make_set()。即将数组中每个元素单独划分成一个个集合，也就是每个元素的祖先节点（和父亲节点）是它本身。假设数组P用来存所有节点,则可表示如下:

for(int i = 0; i < size; i++)  
    p[i] = i;    //其中p[i] = m 表示元素i的父亲节点为m

2.对不同集合进行合并，Union(x,y)。将包含元素x和元素y的两个集合合并成一个集合实，质是对于x和y的祖先节点不是同一节点，把y的祖先点变成x的祖先节点，这样x,y的祖先节点就相同了；(含y的树就变成含x的树的一颗子树了)x,y就属于同一集合了。可表示如下：

void Union(int x,int y)  
{  
    int px = Find(x),py = Find(y);  
    if(px != py)  
    {  
        p[py]=px;  //吧
    }  
}   
  

3.查找元素所在的集合，Find(x)。返回元素x所在的集合，实质是找到x的祖先节点。可表示如下：

int Find (int x)//实质是找到x的祖先节点
{
　　int r = x;
　　while(p[r] != r) //通过不停迭代来找到x的祖先节点
　　r = p[r];
return r;
}

以上是并查集最基本的应用，然而实际问题中，需要对并查集的几种操作进行优化。

1.对Find(x)的优化。

由于Find(x)是找到x的祖先节点，寻找祖先时我们一般采用递归查找，但是当元素很多亦或是整棵树变为一条链时，每次Find(x)都是O(n)的复杂度，此时Find函数的性能比较差。

此时，可考虑"路径压缩"的方法，来减少查找次数。即经过"递推"找到祖先节点后，"回溯"的时候顺便将它的子孙节点都直接指向祖先，这样以后再次Findt(x)时复杂度就变成O(1)了，所以树的结构变成如下的形式:

其具体操作如下：

int Find(int x)//返回x的祖先节点
{
    if (x != p[x])
    {
       p[x] = Find(p[x]); //回溯进行路径压缩，此处用的递归实现，递归便于理解；当然也可以用迭代实现;
    }
    return p[x];
}
 

2.对Union(x,y)的优化。

在上面对Union(x,y)的实现中，每当px!=py时，就让y的祖先节点指向x的祖先节点，如果含y的树的高度大于含x树的高度的话，整棵树就变成了一颗高度更大的树了。树的高度增加，必然带来性能的下降,find函数效率下降。所以我们应该考虑树的大小，然后再来决定到底是调用：

　　p[py] = px 或者是 p[px] = py.

于是现在的问题就变成了：树的大小该如何确定？(此时树的大小称为秩)

可以通过设定一个数组s来存树的大小，在初始情况下，每个组的大小都是1，因为只含有一个节点，对该数组的初始化也很直观：

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

所以初始化函数Make_set()应变为：

void Make_Set()
{
    for (int i = 0; i < size; i++)  
{
        p[i] = i; //初始化集合 
        s[i] = 1; //初始化树的代销
     
}
}

而在进行合并的时候，会首先判断待合并的两棵树的大小，然后按照上面的思想进行合并，此时Union(x,y)又称为按秩合并，其实现代码如下：

 void Union(int x, int y)  
{  
    int px = Find(x);  
    int py = Find(y);  
    if (px == py) 
          return;  
    
    if (sz[px] < sz[py]) // 将小树作为大树的子树  
 {      p[px] = py; 
        s[py] += s[px];
 }  
    else { 
        p[py] = px;  
        s[px] += s[py];
 }  
    
}      

至此，并查集的相关内容介绍完毕。此外，分享一个有趣的相关介绍:http://blog.csdn.net/dellaserss/article/details/7724401/

参考:1.http://www.ahathinking.com/archives/10.html

　　 2.http://blog.csdn.net/dm_vincent/article/details/7655764

restructuringcompany和almostunion-find并查集的区间合并与并查集的删除

RestructuringCompany Eventhemostsuccessfulcompanycangothroughacrisisperiodwhenyouhavetomakeaharddecision—torestructure,discardandmergedepartments,fireemployeesanddootherunpleasantstuff.Let‘sconsi 查看详情

并查集的优化及应用

2018-05-0115:13:08并查集是一个时空复杂度非常优越的数据结构，并且通过优化后其复杂度为<O(1)，O(n)>。并查集的优化主要有两个方面：路径压缩按rank来合并路径压缩：按rank合并：publicclassUnionFindSetprivateint[]parent;privateint[]rank;p... 查看详情

关于并查集的一切全在这里了(代码片段)

文章目录并查集初识「并查集」常用术语「并查集」基本思想「并查集」的两个实现方式QuickFind方式实现并查集QuickFind工作原理：代码实现与验证时间复杂度QuickUnion方式实现并查集QuickUnion的工作原理为什么QuickUnion比QuickFind... 查看详情

并查集的基础

...ss/article/details/7724401/史上最容易理解的解答！没有之一。并查集能实现的功能：判断是否成环，计算共有多少个非连通图。。。待日后填坑在最小生成树中应用并查集最简代码！intf(intx){returnx==pre[x]?x:pre[x]=f(pre[x]);}　　voidmix(inta,... 查看详情

数据结构一篇文章学懂并查集+lrucache，拿来吧你！(代码片段)

并查集--LRUCache并查集的概念一、并查集的用途并查集的结构解释并查集的实现并查集相关习题习题1.leetcode朋友圈习题2.leetcode等式方程的可满足性并查集的思考与提升二、LRUCache的介绍1.什么是LRUCache习题.LRU缓存机制总结好文建... 查看详情

并查集的java实现

Java实现并查集，合并时采用路径压缩算法。如果合并时使用循环修改的方法，一次合并的时间复杂度就为N，无法接受publicclassUnion{publicint[]id;//对应索引所在的集publicint[]sz;//所在集的size，合并时小集合大集publicintcount;publicUnion(in... 查看详情

并查集的基本操作和用法(代码片段)

并查集并查集的作用：1.合并区间2.判断两个数是否再同一个集合之中3.寻找联通子图的的个数并查集的关键函数find(x)与p[]数组寻找x的祖宗节点/* find函数用于寻找祖宗节点*/intfind(intx)if(p[x]!=x) find(p[x])returnp[x];/* p[N] 存储每... 查看详情

并查集的基本操作和用法(代码片段)

并查集并查集的作用：1.合并区间2.判断两个数是否再同一个集合之中3.寻找联通子图的的个数并查集的关键函数find(x)与p[]数组寻找x的祖宗节点/* find函数用于寻找祖宗节点*/intfind(intx)if(p[x]!=x) find(p[x])returnp[x];/* p[N] 存储每... 查看详情

并查集的原理及实现(代码片段)

一、定义　　并查集是一种树型的数据结构，用于处理一些不相交集合（DisjointSets）的合并及查询问题。二、代码实现　　在并查集结构中，用一个pre[]数组来存储当前结点的父亲结点，有两个函数，found()函数用来寻找根结点，... 查看详情

并查集的基本运用poj1611

用并查集的情况是在比如A和B联通 B和C联通那么ABC联通这类情况下算某个元素所在集合的元素个数。.并查集数据结构用数组就行，数组的下标表示相应的一个主体，对应的值表示它的父节点的索引，指向父节点。根节点的值... 查看详情

并查集的理解

...联系起来，而又不想一个一个的将它们绑到一起，那么，并查集就是解决它们之间联系的数据结构。树就是我们需要用到的一种连接结构 查看详情

并查集的小节(代码片段)

寒假就看了并查集的视频，可是一直没怎么用了，现在终于还是拾起，看了这方面的视频还是很好理解的；看了挑战程序竞赛这本后，感觉大佬的思路就是简单，高效，可以首先写几个函数，分部实现各个功能，按照思路：1，... 查看详情

poj2236（并查集的应用）(代码片段)

WirelessNetworkTimeLimit: 10000MS MemoryLimit: 65536KTotalSubmissions: 35832 Accepted: 14863DescriptionAnearthquaketakesplaceinSoutheastAsia.TheACM(AsiaCooperatedMedicalt 查看详情

数据结构--并查集的原理及实现(代码片段)

一，并查集的介绍 并查集（Union/Find）从名字可以看出，主要涉及两种基本操作:合并和查找。这说明，初始时并查集中的元素是不相交的，经过一系列的基本操作(Union)，最终合并成一个大的集合。而在某次合并之后，有一种... 查看详情

并查集的初步认识

...你他们是否有联系？如何快速解决这类问题，这时候需要并查集并查集意思是说，有个类似指针的东西，将子节点连接父节点，那么这个时候，父子节点是连接的，如果父节点是根节点，那么父节点的指针指向自己；这里让父节... 查看详情

数据结构——并查集的详细解析和实现(代码片段)

...帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦一.并查集的定义1.并查集是一种树型的数据结构，用于处理一些不相交集合（disjointsets）的合并及查询问题。2.并查集通常包含两种操作查 查看详情

数据结构——并查集的详细解析和实现(代码片段)

...帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦一.并查集的定义1.并查集是一种树型的数据结构，用于处理一些不相交集合（disjointsets）的合并及查询问题。2.并查集通常包含两种操作查 查看详情

almostunion-find并查集的删除

AlmostUnion-FindIhopeyouknowthebeautifulUnion-Findstructure.Inthisproblem,you‘retoimplementsomethingsimilar,butnotidentical.Thedatastructureyouneedtowriteisalsoacollectionofdisjointsets,supporting3ope 查看详情