并查集模板

发表于 | 更新于

标准

(自改型和其一样，查询为O(1), 路径压缩 + 按秩合并)

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
const int MN = 50;
int par[MN], heig[MN];
void init(int n)		//初始化 每个点的根节点先初始化为自己，此时树的高度为0 
{
	for(int i = 0; i < n; i ++)			
		par[i] = i;
}

int find(int x)			//查找根节点 
{
	if(par[x] == x)	return x;		//如果找到根节点直接返回（刚开始根节点都初始化为本身） 
	return par[x] = find(par[x]);				//递归的进行寻找，从父节点一个一个往上找 
}

void unite(int x, int y)		//合并 
{
	x = find(x);			//由于函数里是备份不会改变原有值直接操作 
	y = find(y);	//找到x，y的根节点 
	if(x == y)	return;			//如果x，y的根节点相同则不用合并 
	if(heig[x] < heig[y])			//如果y的深度大于x的深度，x接到y上(出于树防树退化的考虑) 
		par[x] = y;							//x的根节点变为y的 
	else
	{
		par[y] = x;		  //否则y接x上 
		if(heig[x] == heig[y])	heig[x] ++;		//如果出现深度相同的情况，那么x的深度+1(深度相等情况的处理) 
	}
}
bool same(int x, int 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
const int N = 
par[N], heig[N];
void init()
{
    for(int i = 0; i < n; i ++)
        par[i] = i;
}

int find(int x)
{
    if(par[x] == x)
        return x;
    return par[x] = find(par[x]);
}

void unite(int x, int y)
{
    x = find(x), y = find(y);
    if(x == y)  return;
    if(heig[x] > heig[y])   par[y] = x;
    else if(heig[x] == heig[y])   par[y] = x, heig[x] ++;
    else    par[x] = y;
}

bool same(int x, int y)
{
    return find(x) == find (y);
}

并查集 lyd版

(查询logn，只用了路径压缩）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void init()
{
	for(int i = 0; i < n; i ++)		a[i] = i;
}

int get(int x)
{
	return x == f[x] ? x : f[x] = get(f[x]);
}
void merge(int x, int y)
{
	f[get(x)] = get(y);			//直接将x的根节点连在y的根节点上
}

bool same(int x, int y)
{
	return get(x) == get(y);
}
0%