带路径压缩和秩的并查集
作者:
Chongyu
,
2023-03-21 12:47:38
,
所有人可见
,
阅读 150
带路径压缩和秩的并查集
#include<iostream>
using namespace std;
int Father[10000000] = { 0 };
void makeSet(int x) {
Father[x] = -1;
}
int Find(int x) {
if (Father[x] < 0) {
return x;
}
int fp = Find(Father[x]);
Father[x] = fp;
return fp;
}
void Union(int x, int y) {
int rx = Find(x);
int ry = Find(y);
if (rx == ry)return;
if (Father[rx] < Father[ry]) {
Father[ry] = rx;
}
else {
Father[rx] = ry;
if (Father[rx] == Father[ry]) {
Father[ry]=Father[ry]-1;
}
}
}