并查集总结

目录

一、并查集

二、带权并查集

---

一、并查集

每当学习一个新算法，真的不得不感叹算法真的……博大精深！！

先分享一篇大佬的博客晚上再来补文，讲的太有意思了，一看就能明白，要是每个算法都有人这么有趣生动地给我讲就好了。

https://blog.csdn.net/u013546077/article/details/64509038

简单来说并查集就是用来判断连通性滴，核心代码如下。

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

 

int pre[1000];
int find(int x)//查找根节点
{
	int r=x;
	while(pre[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;
 }

 

【题目】

【HDU1232】通畅工程

【HDU1272】小希的迷宫（判断无向图是否有回路）

 

二、带权并查集

• 定义：带权并查集即是结点存有权值信息的并查集。
• 适用：当两个元素之间的关系可以量化，并且关系可以合并时，可以使用带权并查集来维护元素之间的关系。
• 权值：带权并查集每个元素的权通常描述其与并查集中祖先的关系，这种关系如何合并，路径压缩时就如何压缩。
• 与并查集的区别：带权并查集可以推算集合内点的关系，而一般并查集只能判断属于某个集合。

带权值的并查集只不过是在并查集中加入了一个value[ ]数组，value[ ]可以记录很多种东西，不一定是类似距离这种东西，也可以是相对于根节点的状态，加入了权值，函数应该有一些改变。

int findroot(int x)
{
    if(x!=pre[x])
    {
        int t=pre[x];
        pre[x]=findroot(pre[x]);//路径压缩
        value[x]+=value[t];//该点到根的距离
    }
    return pre[x];
}