并查集的简单学习笔记

并查集

1. 结构：用树形结构来实现，每个元素表示一个节点，每个组是一棵树。
2. 查询：可以查询两个元素是否在一个组，从结点开始往上找，看根节点是否相同。均摊查询复杂度是O（n）。
3. 合并：可以将两个组 合并为一个组，将树的根节点相连接。
   （1）树的高度小的向高度大的连边
   （2）路径压缩（每次查找时，查询过程中向上经过的所有结点都修改为直接指向根，但为了简单不修改树的高度）

代码实现

1. 初始化
2. 查找根节点
3. 合并操作
4. 判断是否属于同一个集合

#include
#define N 9999
using namespace std;

int par[N];//记录结点编号为i的父亲的编号
int rank[N]；//树的高度

void init(int n) { //初始化
	for(int i=0; i<n; i++) {
		rank[i]=0;//此时树的高度是0
		par[i]=i;//自己是自己的父亲，即单独的结点
	}
}

int find (int x) { //查询结点x所在树的根结点
	if(par[x]==x) { // 如果自己是自己的父亲，说明该结点是根节点
		return x;//返回跟结点
	} else { //如果自己不是根节点，则继续查找
		return par[x]=find(par[x]);
		//查找的时候，让经过的子节点直接指向根节点，即路径压缩，但是不修改树的高度
	}
}

void unite(int x,int y) {//合并x和y的所属的集合 
	x=find(x);//获得根节点 
	y=find(y);
	if(x==y)
		return;
	if(rank[x]<rank[y]) { //树的高度小的向高度大的连边
		par[x]=y;
	} else {
		par[y]=x;
		if(rank[x]==rank[y])
			rank[x]++;
	}
}

bool same(int x,int y){//判断x y是否属于同一个集合 
	return find(x)==find(y);
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40