图算法总结(并查集) - 综合当前位置:& &&&图算法总结(并查集)图算法总结(并查集)&&网友分享于：&&浏览：0次图算法小结(并查集)一：起因
（1）关于图的算法一般是比较复杂的，自己在这方面也是比较弱的，首先是图的存储问题 和 遍历问题：
存储分为两种，邻接矩阵 和 临街表；遍历分为DFS 和 BFS两种，非常类似于二叉树的先跟遍历和层次遍历。
（2）图在实际应用中是非常广泛的，这与万物归一，万物相连的理论是一致的，两个物体之间有着千丝万缕的联系，我们成这种联系建立的网络为图（带权图）；联系的强弱为边的权重。
（3）图的一些复杂的算法，也是建立在两种遍历图的思想的基础上进行的，所以我们先从简单的谈起。
（4）图的相关知识：
图的定义：
& & & &很简单，G(V,E)， V、E分别表示点和边的集合。 & & &&
图的表示：
& & & &主要有两种，邻接矩阵和邻接表，前者空间复杂度，O(V2），后者为O(V+E)。因此，除非非常稠密的图(边非常多），一般后者优越于前者。
图的遍历：
& & & &宽度遍历BFS(start): & &(1) 队列Q=Empty，数组bool visited[V]={false...}. Q.push(start);
& & & & & & & & & & & & & & & & & & & & & & &(2) while (!Q.empty()){
& & & & & & & & & & & & & & & & & & & & & & & & & & & &u = Q.pop(); &visited[u] = & //遍历u结点
& & & & & & & & & & & & & & & & & & & & & & & & & & & &foreach (u的每一个邻接结点v) Q.push(v);
& & & & & & & & & & & & & & & & & & & & & & & & & & } &&
& & & &深度遍历DFS(start): & & (1) 栈S=Empty, 数组bool visited[V]={false...}. S.push(start);
& & & & & & & & & & & & & & & & & & & & & & & &(2) while (!S.empty()){
& & & & & & & & & & & & & & & & & & & & & & & & & & & &u = S.pop();
& & & & & & & & & & & & & & & & & & & & & & & & & & & &if (!visited[u]) visited[u] = & //遍历u结点
& & & & & & & & & & & & & & & & & & & & & & & & & & & &foreach (u的每一个邻接结点v) S.push(v);
& & & & & & & & & & & & & & & & & & & & & & & & & & }
& & & 两个算法很相似，主要区别在于一个使用队列，一个使用栈。队列是先入先出，所以访问u以后接下来就访问u中未访问过的邻接结点；而栈的后进先出，当访问u后，压入了u的邻接结点，在后面的循环中，首先访问u的第一个临接点v，接下来又将v的邻接点w压入S，这样接下来要访问的自然是w了。
最小生成树：
& & & &(1)Prime算法: & &(1) 集合MST=T=Empty，选取G中一结点u，T.add(u)
& & & & & & & & & & & & & & & & & (2) 循环|V|-1次：
& & & & & & & & & & & & & & & & & & & & 选取一条这样的边e=min{(x,y) | x in T, y in V/T}
& & & & & & & & & & & & & & & & & & & & T.add(y); MST.add(e);
& & & & & & & & & & & & & & & & & (3) MST即为所求
& & & &(2) Kruskal算法 & (1) 将G中所有的边排序并放入集合H中，初始化集合MST=Empty,初始化不相交集合T={{v1}, {v2}...}}，也即T中每个点为一个集合。
& & & & & & & & & & & & & & & & & & (2) &依次取H中的最短边e(u,v)，如果Find-Set(u)!=Find-Set(v)（也即u、v是否已经在一棵树中），那么Union(u,v) （即u,v合并为一个集合)，MST.add(e);
& & & & & & & & & & & & & & & & & & (3) MST即为所求
& & & &这两个算法都是贪心算法，区别在于每次选取边的策略。证明该算法的关键在于一点：如果MST是图G的最小生成树，那么在子图G'中包含的子生成树MST' 也必然是G'的最小生成树。这个很容易反正，假设不成立，那么G'有一棵权重和更小的生成树，用它替换掉MST'，那么对于G我们就找到了比MST更小的生成树，显然这与我们的假设(MST是最小生成树)矛盾了。
& & & &理解了这个关键点，算法的正确性就好理解多了。对于Prime，T于V/T两个点集都会各自有一棵生成树，最后要连起来构成一棵大的生成树，那么显然要选两者之间的最短的那条边了。对于Kruskal算法，如果当前选取的边没有引起环路，那么正确性是显然的（对给定点集依次选最小的边构成一棵树当然是最小生成树了），如果导致了环路，那么说明两个点都在该点集里，由于已经构成了树（否则也不可能导致环路）并且一直都是挑尽可能小的，所以肯定是最小生成树。
& & & &这里的算法基本是基于动态规划和贪心算法的，经典算法有很多个，主要区别在于：有的是通用的，有的是针对某一类图的，例如，无负环的图，或者无负权边的图等。
& & & &单源最短路径（1） 通用（Bellman-Ford算法）：
& & & & & & & & & & & & & & & &（2） 无负权边的图(Dijkstra算法)：
& & & & & & & & & & & & & & & &（3） 无环有向图(DAG) ：
& & & &所有结点间最短路径：
& & & & & & & & & & & & & & & &（1） Floyd-Warshall算法：
& & & & & & & & & & & & & & & &（2） Johnson算法：
关键路径 和&拓扑排序:
二：代码示例
（1）最简单的图的遍历问题
Lake Counting
Sample Input
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
Sample Output
要求输出图中连通分支的个数，最简单的图遍历问题。
图的常见遍历方式有两种：深度优先遍历和广度优先遍历，他们的作用是将图中的每个点都访问一遍，只不过是顺序不同。
如果把图中的每条边长都相等（比如都是1）的话，深度优先遍历过程就是尽可能深的去访问节点，具体过程为：
1.任意选定一个点p0作为遍历的起点
2.当访问到某一个节点p1时，如果p1下面有未被遍历的子节点，我们就接着访问p1的某一个未被遍历子节点，并标记该子节点被访问过，
3.如果p1不存在未被访问的子节点，我们就退回到p1的父节点，并执行第2步
4.执行第2、3步，直到所有节点被访问过。
大家也看出来了，深度优先遍历的是一个递归的过程，因此很容易想到要用到栈这种数据结构，具体实现的时候可以用递归，也可以用栈。看个人习惯了。
广度优先遍历实现就要用到队列了。以下是poj2386不同实现方式的代码
#include &iostream&
#include &string&
const int MAX_SIZE = 102;
string strs[MAX_SIZE];
int dir[8][2] = {{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1}};
inline bool isBound(int x,int y)
return (x&0 || x&=m || y&0 || y&=n);
void dfs(int xindex,int yindex)
strs[xindex][yindex] = '.';
int i,x,y;
for(i=0; i&8; ++i)
x = xindex+dir[i][0];
y = yindex+dir[i][1];
if(!isBound(x,y) && strs[x][y]=='W')
int main()
cin && m &&
getline(cin,strs[0]);//¿ÕÐйýÂË
for(i=0; i&m; ++i)
getline(cin,strs[i]);
//cout && strs[i] && & i= & && i &&
int ans = 0;
for(i=0; i&m; ++i)
for(j=0; j&n; ++j)
if(strs[i][j]=='W')
//cout && strs[i][j];
cout && ans &&
（2）最小生成树 ---- prime实现 O(N2)
题意：北极有一些村庄，现需要在这些村庄间建立起通讯，有s个卫星频道，任何两个拥有卫星频道的村庄都可以直接通过卫星进行通讯而无视距离，没有卫星的村庄通过无线电进行通讯，并且这两个村庄的距离不能超过D，D值取决于无线电收发器的功率，功率越大，D值越大，但价格也越高，出于购买费用和维护费用的考虑，所有村庄的无线电收发器都相同，即D值相同，现要求在保证任意两个村庄间都能直接或间接通讯，并且D值最小，输出这个最小值。就是输出最小生成树最大边的权值，但是卫星频道是不确定因素。这道题有个很好的解法及证明。
其实题目意思是将一棵最小生成树转化成一个森林，森林里有S棵树，每棵树配一个卫星频道，并且使得森林里所有边中最长的边的长度最小
其实意思就是可以删除最小生成树中的S-1条边，问剩下的边中最长的是多少
由于建图时每两个点之间都有边，是稠密图，故用Prim法比较好 ---- 有的题目也稍微复杂一点，首先得判断是否联通，再求最小生成树
#include &iostream&
#include&cmath&
#include&algorithm&
const int INF = 1000000;
const int MAX_SIZE = 501;
double map[MAX_SIZE][MAX_SIZE];
double path[MAX_SIZE];
struct node
}point[MAX_SIZE];
//记录从顶点集U到V-U的代价最小的边的辅助数组定义
}closedge[MAX_SIZE];
bool cmp(double a,double b)//从大到小偏序
return a&b;
inline double CalDist(struct node
&a, struct node &b)
double xx = (a.x-b.x);
double yy = (a.y-b.y);
return sqrt(xx*xx + yy*yy);
//用普里姆算法从第k个顶点出发构造网G的最小生产树T,N个顶点的图
void prim(int k,int n)
for(j=1;j&=n;j++)//辅助数组初始化
closedge[j].adjvex=k;
closedge[j].lowcost=map[k][j];
closedge[k].lowcost=0; //初始，U={u},这里将0作为访问过的标志
for(i=1;i&n;i++)//选择其余n-1个顶点，这个i不无任何实际意义，仅仅是选取n-1个点，记录次数而已
double min=INF;
for(j=1;j&=n;j++)//求出T的下一个结点：第k顶点，最小的，不成环（即未访问过）
if(closedge[j].lowcost!=0&&min&closedge[j].lowcost)
min=closedge[j].
closedge[k].lowcost=0; //第k顶点并入U集
path[l++]=map[k][closedge[k].adjvex]; //保存该边，要是求最小生成树的成本，就得改成加和了，要是求最小生成树的最大边权值，就得比较最大值了
for(j=1;j&=n;j++) //新顶点并入U后重新选择最小边
if(map[k][j]&closedge[j].lowcost)
closedge[j].adjvex=k;
closedge[j].lowcost=map[k][j];
}// end of for
}// end of for
int main()
int t,m,n;
while(t--)
cin&&m&&n;
for(i=1;i&=n;i++)
cin&&point[i].x&&point[i].y;
// init dist
for(i=1;i&=n;i++) //求出毎两个顶点之间的距离
for(j=1;j&i;j++)
map[i][j]=map[j][i]=CalDist(point[i],point[j]);
//cout && map[i][j] &&
for(i=1;i&=n;i++)
map[i][i]=INF;
prim(1,n);
sort(path,path+n-1,cmp); //把构成最小生成树的n-1条边从大到小排序
cout.setf(ios::fixed);//保留两位小数
cout.precision(2);
cout&&path[m-1]&&//数组d从下标0开始存储，即第m条边
（3）最小生成树的变种 ---- 求最小生成树的最大权值的边，并查集实现kruskal算法 O(eloge)
Help Bessie know the largest amount of water she will ever have to carry:
what is the length of longest road she'll have to travel between any two farms,
presuming she chooses routes that minimize that number? This means, of course,
that she might backtrack over a road in order to minimize the length of the longest road she'll have to traverse.
即农民遍历每一个农场需要的最少带水量，到达每一个农场，他都可以补充水分的。
最小生成树的最大边
#include &cstdio&
#include &cstdlib&
const int MAX_SIZE = 2500000;
const int MAX_POINT = 2001;
struct Edge
}E[MAX_SIZE];
int set[MAX_POINT];
// c里面的qsort函数
int cmp(const void *a,const void *b)
struct Edge *c,*d;
c=(struct Edge *)a;
d=(struct Edge *)b;
return c-&len - d-&
// 并查集的建立
void build(int num)
for(i=1;i&=i++)
int find(int k)
if(set[k]==k)
set[k]=find(set[k]);
return set[k];
void Union(int f1,int f2)
set[f1]=f2;
inline int MAX(int a,int b)
return a&b?a:b;
int Krustal(const int edges)
int f1,f2;
//初始状态 均为访问过
for(i=0; i!= ++i)
E[i].flag=0;
//用并查集 实现的克鲁斯卡尔核心算法，
//当然代码需要优化的地方很多，例如当nion的个数等于n-1时，即可停止;
//以及上下两个for循环可以同时合并到中间的for里面
for(i=0; i!= ++i)
f1=find(E[i].ori);
f2=find(E[i].des);
if(f1==f2)
Union(f1,f2);
E[i].flag=1;
// 求最小生成树的最大权边
for(i=0; i!= ++i)
if(E[i].flag)
ans=MAX(ans,E[i].len);
int main()
int ori,des,
while(scanf(&%d%d&,&n,&m)!=-1)
build(n);// 建立并查集
for(int i=0; i!=m; ++i)
scanf(&%d%d%d&,&ori,&des,&len);
qsort(E,m,sizeof(E[0]),cmp);
printf(&%d\n&,Krustal(m));
12345678910
12345678910
12345678910 上一篇：下一篇：文章评论相关解决方案 1234567891011 Copyright & &&版权所有并查集 - VincentCZW - 博客园
评论 - 381
1.引出并查集
&&&&&&&& 并查集，英文译为Disjoint Set，即不相交集合。常用来解决集合相交问题。为什么叫并查集呢？这是因为并查集中包括两个主要的步骤：（1）合并（2）查找。不妨看看下面的例题：
& &在某个城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：
n& & 我朋友的朋友是我的朋友；
n& & 我敌人的敌人是我的朋友；
&&&&&& 已知关于 n个人的m条信息（即某2个人是朋友或者敌人），假设所有是朋友的人一定属于同一个团伙，请计算该城市最多有多少团伙？
&&&&&&&& 分析：要知道有多少个团伙，就要知道每个人属于哪个团伙？还有做到的是若A属于Team1同时也属于Team2那么就要合并Team1和Team2。这就是并查集的&并&和&查&了。显然天生就要用到并查集解决这个题了。
2.并查集实现
&&&&&&&& 2.1现在来看看怎么实现并查集算法吧？主要看看并（merge）和查（find）怎么实现？
还是举个例子吧。存在下面的几个集合{1,3,7}, {4}, {2,5,9,10}, {6,8}，如果用编号最小的元素标记所在集合即为set[i]。表示如下：
&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&& & i&& &&& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10
&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&& set[i]&&&&&&& 1& 2& 1& 4& 2&& 6& 1& 6& 2&& 2
对应的代码：
&&& return set[x];
Merge1(a,b)
&&&&&&&& i = min(a,b);
&&& j = max(a,b);
for (k=1; k&=N; k++)
& &&&&&&if (set[k] == j)
&&&&&&&&&&& set[k] =
Find的时间复杂度为O（1）,merge的时间复杂度为O(N)。那么能不能优化呢？？
&&&&&&&& 2.2并查集中的集合要是表示成树，难道不是很顺理成章的事情吗？？我们试一试吧。
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& & i&& &&& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10
&&&&&&&& &&&&&&&&&&&&&&&&&&&&&&&&&&& set[i]&&&&&&& 1& 2 &&3& 2& 1& 3& 4& 3& 3&& 4
&&&&&&&& set[i] = i , 则i表示本集合，并是集合对应树的根
&&&&&&&& set[i] = j, j&&i, 则 j 是 i 的父节点.
&&&&&&&& 对应的数结构
&&&&&&&&&&&&&&&&&&&&&&&&&&& 1&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 2&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 3
&&&&&&&&&&&&&&&&&&&&&&&&&&& |&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& |&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& |&&&&&& |&&&&&& |
&&&&&&&&&&&&&&&&&&&&&&&&&&& 5&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 4&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 6&&&&&& 8&&&&&& 9
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& |&&&&&&&&&&&&&&& |
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 7&&&&&&&&&&&&&&& 10
&& while (set[r] != r)
&&&&& r = set[r];
merge2(a, b)
&&& if (a&b)
&&&&&& set[b] =
&&&&&& set[a] =
Find的最坏的情况时间复杂度是O(N),merge的复杂度为O(1)，那么这个优化了吗？这就要避免find出现最坏的情况了。其实可以将深度小的树合并到深度大的树。这样假设两棵树的深度分别为h1和h2, 则合并后的树的高度h是:
1.max(h1,h2), if h1&&h2.
2.h1+1, if h1=h2.
看看代码优化过的代码吧？（find没有变化，变化的merge）
merge3(a,b)
&&&&&&&& if (height(a) == height(b))
&&&&&&&& {
&&& &&&&&&&& height(a) = height(a) + 1;
&&&&&& & set[b] =
&& else if (height(a) & height(b))
&&&&& set[a] =
&&&&& set[b] =&
这样优化过后，显然树的高度不会超过logN了。这样find的复杂度也就不会是O（n）了吧。
&&&&&&&& 2.3作为一个IT应该善于思考滴，想想还能不能优化呢？这一次我们采取一种叫做路径压缩的技术进行优化。思路是这样的：第一步，找到根结点。第二步，修改查找路径上的所有节点，将它们都指向根结点。这显然可以缩短find的复杂度吧。看看代码：
&&&&&&&& r =
&&&&&&&& while (set[r] && r) //找根节点
&&&&&&&&&&&&&&&&&& r = set[r];&&&&&&
&&&&&&&& i =
&&&&&&&& while (i && r) //修改查找路径中所有节点指向根节点
&&&&&&&& {&&
&&&&&&&&&&&&&&&&&& j = set[i];
& set[i] =
3．总结一下：
&&&&&&&& 并查集算法的时间复杂度主要是find和merge。2.2和2.3的优化本质上都是从find上面优化的，方法都是降低树的高度。2.2是合并的降低的；2.3是查找根节点的时候降低的。另外我们在用并查集的时候，只需要调用merge的。
Problem Description
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府&畅通工程&的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( & 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。 注意:两个城市之间可以有多条道路相通,也就是说3 31 21 22 1这种输入也是合法的当N为0时，输入结束，该用例不被处理。
对每个测试用例，在1行里输出最少还需要建设的道路数目。
Sample Input
Sample Output
#include "stdio.h"
int bin[1002];
int findx(int x)
&&& int r=x;
&&& while(bin[r] !=r)
&&&&&&& r=bin[r];
void merge(int x,int y)
&&& int fx,
&&& fx = findx(x);
&&& fy = findx(y);
&&& if(fx != fy)
&&&&&&& bin[fx] =
int main()
&&& int n,m,i,x,y,
&&& while(scanf("%d",&n),n)
&&&&&&& for(i=1;i&=n;i++)
&&&&&&&&&&& bin[i] =
&&&&&&& for(scanf("%d",&m);m&0;m--)
&&&&&&&&&&& scanf("%d %d",&x,&y);
&&&&&&&&&&& merge(x,y);
&&&&&&& for(count=-1, i=1;i&=n;i++)
&&&&&&&&&&& if(bin[i] == i)
&&&&&&&&&&&&&&& count ++;
&&&&&&& printf("%d\n",count);
阅读(...) 评论()5222人阅读
并查集小结
并查集大体分为三个：普通的并查集，带种类的并查集，扩展的并查集（主要是必须指定合并时的父子关系，或者统计一些数据，比如此集合内的元素数目。）
经典的种类并查集
用并查集来判断一棵树。。注意空树也是树，死人也是人。
裸地水并查集
种类并查集
看上去似乎和种类并查集无关，但其实仔细想想，就是种类并查集。。。
只不过是种类数目无穷大，通过合并，可以确定两个物品之间的种类差（即高度差）
裸地并查集，小加一点计算几何
裸地种类并查集
又是裸地并查集
常规思想是贪心+堆优化，用并查集确实很奇妙。。。下面的文章中有详细介绍。
种类并查集，先要离散化一下，不影响结果。。。
上一道题的扩展，也是种类并查集，种类无穷大。。。。
种类并查集，然后需要背包原理来判断是否能唯一确定“好人”那一堆
baidu的题，AC了，不过有点乱，有时间【【【再看看】】】
ZOJ-3261&& NUAA-1087
逆向使用并查集就可以了。。。
POJ-1861& POJ-2560
Kruskal并查集
另外这个文章很好：
&&&&& 继续数据结构的复习，本次的专题是：并查集。
&&&&& 并查集，顾名思义，干的就是“并”和“查”两件事。很多与集合相关的操作都可以用并查集高效的解决。
&&& && 两个操作代码：
&&&&&& int Find(int x)
&&&&&&&&& if (tree[x].parent != x)
&&&&&&&&& {
&&&&&&&&&&&&& tree[x].parent = Find(tree[x].parent);
&&&&&&&&& }
&&&&&&&&& return tree[x].
&&&&&& void Merge(int a, int b, int p, int q, int d)
&&&&&&&&& if (tree[q].depth & tree[p].depth) tree[p].parent =
&&&&&&&&& else
&&&&&&&&& {
&&&&&&&&&&&&& tree[q].parent =
&&&&&&&&&&&&& if (tree[p].depth == tree[q].depth) tree[p].depth++;
&&&&&&&&& }
&&&&&& 其中Find()函数用了路径压缩优化，而Merge()函数用了启发式合并的优化(个人感觉有了路径压缩，启发式合并优化的效果并不明显，而经常因为题目和代码的限制，启发式合并会被我们省略)。
&&&&&& 提到并查集就不得不提并查集最经典的例子：食物链。
&&&&&& POJ 1182 食物链
&&&&&& 题目告诉有3种动物，互相吃与被吃，现在告诉你m句话，其中有真有假，叫你判断假的个数(如果前面没有与当前话冲突的，即认为其为真话)
这题有几种做法，我以前的做法是每个集合(或者称为子树，说集合的编号相当于子树的根结点，一个概念)中的元素都各自分为A, B, C三类，在合并时更改根结点的种类，其他点相应更改偏移量。但这种方法公式很难推，特别是偏移量很容易计算错误。
下面来介绍一种通用且易于理解的方法：
首先，集合里的每个点我们都记录它与它这个集合(或者称为子树)的根结点的相对关系relation。0表示它与根结点为同类，1表示它吃根结点，2表示它被根结点吃。
那么判断两个点a, b的关系，我们令p = Find(a), q = Find(b)，即p, q分别为a, b子树的根结点。
&&&&&& 1. 如果p != q，说明a, b暂时没有关系，那么关于他们的判断都是正确的，然后合并这两个子树。这里是关键，如何合并两个子树使得合并后的新树能保证正确呢？这里我们规定只能p合并到q(刚才说过了，启发式合并的优化效果并不那么明显，如果我们用启发式合并，就要推出两个式子，而这个推式子是件比较累的活…所以一般我们都规定一个子树合到另一个子树)。那么合并后，p的relation肯定要改变，那么改成多少呢？这里的方法就是找规律，列出部分可能的情况，就差不多能推出式子了。这里式子为 : tree[p].relation
= (tree[b].relation – tree[a].relation + 2 + d) % 3; 这里的d为判断语句中a, b的关系。还有个问题，我们是否需要遍历整个a子树并更新每个结点的状态呢？答案是不需要的，因为我们可以在Find()函数稍微修改，即结点x继承它的父亲(注意是前父亲，因为路径压缩后父亲就会改变)，即它会继承到p结点的改变，所以我们不需要每个都遍历过去更新。
&&&&&& 2. 如果p = q，说明a, b之前已经有关系了。那么我们就判断语句是否是对的，同样找规律推出式子。即if ( (tree[b].relation + d + 2) % 3 != tree[a].relation ), 那么这句话就是错误的。
&&&&&& 3. 再对Find()函数进行些修改，即在路径压缩前纪录前父亲是谁，然后路径压缩后，更新该点的状态(通过继承前父亲的状态，这时候前父亲的状态是已经更新的)。
&&&&&& 核心的两个函数为：
&&&&&& int Find(int x)
&&&&&&&&&& int temp_p;
&&&&&&&&& if (tree[x].parent != x)
&&&&&&&&& {
&&&&&&&&&&&&& // 因为路径压缩，该结点的与根结点的关系要更新(因为前面合并时可能还没来得及更新).
&&&&&&&&&&&&& temp_p = tree[x].
&&&&&&&&&&&&& tree[x].parent = Find(tree[x].parent);
&&&&&&&&&&&&& // x与根结点的关系更新(因为根结点变了)，此时的temp_p为它原来子树的根结点.
&&&&&&&&&&&&& tree[x].relation = (tree[x].relation + tree[temp_p].relation) % 3;
&&&&&&&&& }
&&&&&&&&& return tree[x].
&&&&&& void Merge(int a, int b, int p, int q, int d)
&&&&&&&&& // 公式是找规律推出来的.
&&&&&&&&& tree[p].parent = // 这里的下标相同，都是tree[p].
&&&&&&&&& tree[p].relation = (tree[b].relation – tree[a].relation + 2 + d) % 3;
&&&&&& 而这种纪录与根结点关系的方法，适用于几乎所有的并查集判断关系(至少我现在没遇到过不适用的情况…可能是自己做的还太少了…)，所以向大家强烈推荐～～
&&&&&& 搞定了食物链这题，基本POJ上大部分基础并查集题目就可以顺秒了，这里仅列个题目编号:&POJ 03 92 2524。
&&&&&& 下面来讲解几道稍微提高点的题目:
&&&&&& POJ 1456 Supermarket
&&&&&& 这道题贪心的思想很明显，不过O(n^2)的复杂度明显不行，我们可以用堆进行优化，这里讲下并查集的优化方法(很巧妙)。我们把连续的被占用的区间看成一个集合(子树)，它的根结点为这个区间左边第一个未被占用的区间。
先排序，然后每次判断Find(b[i])是否大于0，大于0说明左边还有未被占用的空间，则占用它，然后合并(b[i], Find(b[i]) – 1)即可。同样这里我们规定只能左边的子树合并到右边的子树(想想为什么～～)。
&&&&&& POJ 1733 Parity game
&&&&&& 这题同样用类似食物链的思想。
首先我们先离散化，因为原来的区间太大了(10^9)，我们可以根据问题数目离散成(10^4)。我们要理解，这里的离散化并不影响最终的结果，因为区间里1的奇偶个数与区间的大小无关(这句话有点奇怪，可以忽略…)，然后每次输入a, b，我们把b++，如果他俩在一个集合内，那么区间[a, b]里1的个数相当于b.relation ^ a.relation，判断对错即可。如果不在一个集合内，合并集合(这里我们规定根结点小的子树合并根结点大的，所以要根据不同情况推式子)，修改子树的根结点的状态，子树的其他结点状态通过Find()函数来更新。
&&&&&& hdu 3038 How Many Answers Are Wrong
&&&&&& 上面那题的加强版，不需要离散化，因为区间的和与区间的大小有关(和上面的那句话对比下，同样可以忽略之…)，做法与上面那题差不多，只是式子变了，自己推推就搞定了。但这题还有个条件，就是每个点的值在[0, 100]之间，那么如果a, b不在一个子树内，我们就合并，但在合并之前还要判断合并后会不会使得区间的和不合法，如果会说明该合并是非法的，那么就不合并，同样认为该句话是错误的。
&&&&&& POJ 1417 True Liars(难)
&&&&&& 并查集 + DP(或搜索)。
&&&&&& 题目中告诉两种人，一种只说真话，一种只说假话。然后告诉m条语句，问是否能判断哪些人是只说真话的那类人。
&&&&&& 其实并查集部分跟食物链还是相似，而且种类变少了一种，更容易了。我们可以通过并查集把有关系的一些人合并到一个集合内(具体方法参见食物链讲解)。
&&&&&& 现在的问题转化为，有n个集合，每个集合都有a, b连个数字，现在要求n个集合中各跳出一个数(a或者b)，使得他们之和等于n1(说真话的人数)。而这个用dp可以很好的解决，用f[i][j]表示到第i个集合和为j个的情况数，我们还用过pre[i][j]记录当前选的是a还是b，用于后面判断状态。方程为f[i][j] = f[i – 1][j – a] + f[i – 1][j – b], j &= a, j &= b。如果最后f[n][n1] == 1说明是唯一的情况，输出该情况，否则输出 “no”(多解算no)
&&&&&& 注意点 :
&&&&&& 1. 这题的m, n1, n2都有可能出现0，可以特殊处理，也可以一起处理。
&&&&&& 2. 按上面的dp写法，f[i][j]可能会很大，因为n可以达到三位数。其实我们关心的只是f[i][j] 等于0，等于1，大于1三种情况，所以当f[i][j] & 1时，我们都让它等于2即可。
&&&&&& POJ 2912 Rochambeau(难)
&&&&&& Baidu Star 2006 Preliminary的题目，感觉出的很好，在并查集题目中算是较难的了。其实这题跟食物链完全一个磨子，同样三类食物，同样的互相制约关系。所以食物链代码拿过来改都不需要改。但这题有个judge，他可以出任意手势。于是我们的做法是，枚举每个小孩为judge，判断他为judge时在第几句话出错err[i](即到第几句话能判断该小孩不是judge)。
&&&&&& 1. 如果只有1个小孩是judge时全部语句都是正确的，说明该小孩是judge，那么判断的句子数即为其他小孩的err[i]的最大值。如果
&&&&&& 2. 如果每个小孩的都不是judge(即都可以找到出错的语句)，那么就是impossible。
&&&&&& 3. 多于1个小孩是judge时没有找到出错的语句，就是Can not determine。&&&& ZOJ 3261 Connections in Galaxy War
&&&&&&& nuaa 1087 联通or不连通
&&&&&&& 两题做法差不多，都是反过来的并查集题目，先对边集排序，然后把要删去的边从二分在边集中标记。然后并查集连接没有标记的边集，再按查询反向做就可。第一题合并结点时按照题目要求的优先级合并即可。
&&&&&& 这里介绍的并查集题目，主要都是处理些集合之间的关系(这是并查集的看家本领～～)，至于并查集还有个用处就在求最小生成树的Kruskal算法中，那个是图论中求最小生成树的问题(一般这个难点不在于并查集，它只是用于求最小生成树的一种方法)，就不在这里赘述了～～
czyuan原创，转载请注明出处。
种类并查集报告
POJ-1703&&& POJ-1182&&& POJ-2492都是这种题。
别人的报告，讲得很好
原始地址：
——————————————————————————
本来要先写搜索和DP的报告的，因为前面做的都是搜索和DP，正好昨天做了这道并查集的题目，所以就顺手写下。这道题也让我理解了好长时间，还是很有意义的，网上也没有很详细的解题报告。
因为我是按网上通用分类做的，所以做之前就知道用并查集做，不过这道题是并查集的深入应用，没有其它的那么直观。这里我采用的是和网上主流方法一样的方法，这里先贴出源码再深入解释下。
#include&&iostream&
using&namespace&
struct&point{
}&ufind[50010];
void&init(int&n);
int&find(int&index);
void&unions(int&rootx,&int&rooty,&int&x,&int&y,&int&dkind);
int&main()
&&&&int&n,k,count=0,d,x,y;
&&&&scanf(“%d%d”,&n,&k);
&&&&&&&&init(n);
&&&&&&&&while(k–)
&&&&&&&&&&&&scanf(“%d%d%d”,&d,&x,&y);
&&&&&&&&&&&&if(x&n&||&y&n)
&&&&&&&&&&&&&&&&count++;
&&&&&&&&&&&&else&if(d==2&&&&x==y)
&&&&&&&&&&&&&&&&&&&&count++;
&&&&&&&&&&&&else
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&int&rx=find(x);
&&&&&&&&&&&&&&&&int&ry=find(y);
&&&&&&&&&&&&&&&&if(rx!=ry)
&&&&&&&&&&&&&&&&&&&&unions(rx,ry,x,y,d-1);
&&&&&&&&&&&&&&&&else
&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&if(d==1&&&&ufind[x].kind!=ufind[y].kind)
&&&&&&&&&&&&&&&&&&&&&&&&count++;
&&&&&&&&&&&&&&&&&&&&if(d==2&&&&(ufind[x].kind-ufind[y].kind+3)%3!=1)
&&&&&&&&&&&&&&&&&&&&&&&&count++;
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&}
&&&&&&&&printf(“%d\n”,count);
&&&&return&0;
void&init(int&n)
&&&&for(int&i=1;i&=n;i++)
&&&&&&&&ufind[i].parent=i;
&&&&&&&&ufind[i].kind=0;
int&find(int&index)
&&&&if(index==ufind[index].parent)
&&&&&&&&return&
&&&&temp=ufind[index].
&&&&ufind[index].parent=find(ufind[index].parent);
&&&&ufind[index].kind=(ufind[temp].kind+ufind[index].kind)%3;
&&&&return&ufind[index].
void&unions(int&rootx,&int&rooty,&int&x,&int&y,&int&dkind)
&&&&ufind[rooty].parent=
&&&&ufind[rooty].kind=(-dkind+(ufind[x].kind-ufind[y].kind)+3)%3;
1.这里并查集(ufind)的一个同类集合存放的是根据已有正确推断有关联的点，这里的关联包括了吃，被吃，同类三个关系；
2.关系是通过kind来表示的，其值为0，1，2，如果ufind[1].kind==ufind[2].kind，说明1，2点同类；如果
(ufind[1].kind-ufind[2].kind+3)%3==1，说明1吃2；
3.并查集是按索引部分组织起来的，即同一类的点都有共同的根结点；
4.并查集包括初始化(init)，查找(find)，合并(unions)操作，其中有很多关键点，我都在代码中用红色标记。下面逐一解释这些关键点：
(1)ufind[i].kind=0;种类初始化为0，这个看似很简单，但它其实保证了并查集中每一个类的根结点的kind属性为0，这是后面两个关键式推导的基础；
(2)ufind[rooty].kind=(-dkind+(ufind[x].kind-ufind[y].kind)+3)%3;这句出现在合并操作里面，这里要解释的是，在合并之前每个类的集合中所有父节点为根结点的点以及根结点，它们之间的关系都是正确的，合并之后只保证了合并前原两个集合的根结点之间的关系正确，即在新的合并后的集合中仍保证所有父节点为根结点的点以及根结点之间的关系正确。这样我们在做合并操作时，是通过三个关系推到出预合并的两个根结点(rootx,rooty)之间的正确关系的：x和rootx的关系，y和rooty的系，x和y的关系。这就是这个式子的由来，其中用到了前面说过的rootx和rooty为0的结论。
(3)ufind[index].kind=(ufind[temp].kind+ufind[index].kind)%3;这句出现在查找操作里，作用是将待查找的点到它的根结点所经过的所有点进行两个操作，一是把它们的父节点都设为根结点；二是按照从离根结点最近的那个点开始到待查找的点的顺序把它们与根结点的关系设置成正确值(原先有可能是错误的，因为合并操作只保证了所有父节点为根结点的点以及根结点之间的关系正确)。这样之后这个集合中仍然保证了所有父节点为根结点的点以及根结点之间的关系正确，并且待考察的点的父节点为根结点。下面来解释下为什么要按照从离根结点最近的那个点开始到待查找的点的顺序，这也是这个式子为什么这么写的原因：假设1为根结点，Kind为0，其子节点为2，kind为k2，2的子节点为3，kind为k3；因为每次合并只合并根结点，所以3在1，2合并前的根结点一定是2，即若2的kind为0，则3和2的关系就正确了，但合并时2的kind加上了k2，保证了1与2的关系正确而并没有更新k3(这是因为并查集集合中无法从父节点找到子结点，所以等到查找时，要用到该点时再更新也不迟)，所以此时只要将(k2+k3)%3就可以得到正确的以1为基准的3的kind。接下来，k3的kind修正了，k4可以以k3为基础一样通过此方法修正，直到要查的结点，并把它们全部挂到根结点上。
解释就到这里，我想理解时只要画个图就能容易理解些，即以index和kind为结点做出集合的树状图。这里恰巧是3个关系，若是4个关系我想就要更新并查集单位集合的组织形式了，即要可以从根结点遍历全集和。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：207205次
积分：2621
积分：2621
排名：第11408名
原创：44篇
转载：22篇
评论：106条
(1)(1)(4)(6)(10)(1)(1)(3)(1)(2)(1)(1)(7)(1)(2)(24)