并查集的简介

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

  并查集(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

时间: 10-16

并查集的简介的相关文章

《数据结构与算法分析:C语言描述》复习——第八章“并查集”——并查集

2014.06.18 14:16 简介: “并查集”,英文名为“union-find set”,从名字就能看出来它支持合并与查找功能.另外还有一个名字叫“disjoint set”,中文名叫不相交集合.可能我们倾向于用最短的名字,所以就出现了“并查集”翻译为“disjoint set”的情况.并查集是一种树形结构,但与之前讲的树不同的是,这里的树节点只记录父节点,因此是一对一的,就可以用数组来表示并查集. 图示: 并查集可以认为是一个“森林”,也就是多棵树: 既然是并查集,先看看合并3和5之后结

CodeForces 745C Hongcow Builds A Nation 并查集

题意: 给了你n个城市 m条边 k个政府 每个政府管辖的区域内不能和其他政府的区域有相连 即政府之间不存在路径 问你在维护这种关系的同时 最多再加多少条边 思路: 先找出来每个联通块 再找出来没有归属的孤立的点 把他们都放到最大的联通块里 然后每个联通块之间的点两两连边是n*(n-1)/2条边 最后算出来的ans-m就好了 (看别人的博客学了一个max_element 1 #include<bits/stdc++.h> 2 #define cl(a,b) memset(a,b,sizeof(a

并查集(个人模版)

并查集: 1 int find(int a) 2 { 3 int r=a; 4 while(f[r]!=r) 5 r=f[r]; 6 int i=a; 7 int j; 8 while(i!=r) 9 { 10 j=f[i]; 11 f[i]=r; 12 i=j; 13 } 14 return r; 15 } 16 int merge(int a,int b) 17 { 18 int A,B; 19 A=find(a); 20 B=find(b); 21 if(A!=B) 22 { 23 f[B

并查集应用

题目描述: One way that the police finds the head of a gang is to check people's phone calls. If there is a phone call between A and B, we say that A and B is related. The weight of a relation is defined to be the total time length of all the phone calls

【bzoj3674】 可持久化并查集加强版

http://www.lydsy.com/JudgeOnline/problem.php?id=3674 (题目链接) 题意 维护并查集3个操作:合并:回到完成第k个操作后的状态:查询. Solution 其实就是用主席树的叶子节点维护并查集的可持久化数组fa[]. 细节 终于认识到了按秩合并的强大,单纯写个路径压缩Re飞,写了路径压缩+按秩合并比单纯的按秩合并每快多少→_→ 代码 // bzoj3674 #include<algorithm> #include<iostream>

BZOJ1015[JSOI2008]星球大战starwar[并查集]

1015: [JSOI2008]星球大战starwar Time Limit: 3 Sec  Memory Limit: 162 MBSubmit: 5253  Solved: 2395[Submit][Status][Discuss] Description 很久以前,在一个遥远的星系,一个黑暗的帝国靠着它的超级武器统治者整个星系.某一天,凭着一个偶然的机遇,一支反抗军摧毁了帝国的超级武器,并攻下了星系中几乎所有的星球.这些星球通过特殊的以太隧道互相直接或间接地连接. 但好景不长,很快帝国又重

HDU 5606 tree 并查集

tree 把每条边权是1的边断开,发现每个点离他最近的点个数就是他所在的连通块大小. 开一个并查集,每次读到边权是0的边就合并.最后Ans?i??=size[findset(i)],size表示每个并查集根的size Ans_i=size[findset(i)],sizeAns?i??=size[findset(i)],size表示每个并查集根的sizesize. #include<cstdio> #include<cstring> #include<algorithm>

HDU 5441 离线处理 + 并查集

题意:给n个节点m条带权值边的无向图.然后q个问题,每次询问点对的数目,点对需要满足的条件是:1)连通:2)其路径的最大权值不能超过询问值. 分析:如果没次询问一次,dfs一次,很可能超时,因此可以用并查集.离线处理,把边按权值排序,把问题按大小排序.然后离线的过程就是不断向图中加边的过程. 比如样例如下: 然后离线处理,排完序后将会是一条一条的加边:问题也排了序,因此是个累加过程... 1 #include <cstdio> 2 #include <iostream> 3 #in

poj1988 Cube Stacking(并查集

题目地址:http://poj.org/problem?id=1988 题意:共n个数,p个操作.输入p.有两个操作M和C.M x y表示把x所在的栈放到y所在的栈上(比如M 2 6:[2 4]放到[1 6]上为[2 4 1 6]),C x为输出x下面有几个数. 思路:并查集每个集合以栈最下面的数为根,维护两个数组num[x]表示x所在集合节点总数,count[x]表示x下方节点个数.每次查找压缩路径的时候更新count(换父节点的时候每轮都把父节点的count加给儿子,就可以一直更新到x所在栈