typedef struct UnionSet {
int *father, *size;
int n;
} UnionSet;
xxxxxxxxxx
UnionSet *init(int n) {
UnionSet *u = (UnionSet *)malloc(sizeof(UnionSet));
u->father = (int *)malloc(sizeof(int) * (n + 1));
u->size = (int *)malloc(sizeof(int) * (n + 1)); // 记录每棵树的节点个数
for (int i = 1; i <= n; i++) {
u->father[i] = i; //自己为一棵树
u->size[i] = 1; // 只有自己一个节点
}
u->n = n;
return u;
}
一般查找
xxxxxxxxxx
int find(UnionSet *u, int x) {
return u->father[x];
}
普通查找
xxxxxxxxxx
int find(UnionSet *u, int x) {
if (x == u->father[x]) return x;
return find(u, u->father[x]);
}
路径压缩
xxxxxxxxxx
int find(UnionSet *u, int x) {
return x == u->father[x] ? u->father[x] : (u->father[x] = find(u, u->father[x]));
}
一般合并
xxxxxxxxxx
int merge(UnionSet *u, int a, int b) {
int fa = find(u, a), fb = find(u, b);
if (fa == fb) return 0;
for (int i = 1; i <= u->n; i++) {
if (u->father[i] != fa) continue;
u->father[i] = fb;
}
return 1;
}
普通合并
xxxxxxxxxx
int merge(UnionSet *u, int a, int b) {
int fa = find(u, a), fb = find(u, b);
if (fa == fb) return 0;
u->father[fa] = fb;
return 1;
}
按高度合并
xxxxxxxxxx
int merge(UnionSet *u, int a, int b) {
int fa = find(u, a), fb = find(u, b);
if (fa == fb) return 0;
if (height[fa] > height[fb]) {
u->color[fb] = fa;
++heigth[fb];
} else {
u->color[fa] = fb;
++heigth[fa];
}
// for (int i = 1; i <= u->n; i++) {
// if (u->color[i] != color_a) continue;
// u->color[i] = color_b;
// }
return 1;
}
按秩合并
xxxxxxxxxx
int merge(UnionSet *u, int a, int b) {
int fa = find(u, a), fb = find(u, b);
if (fa == fb) return 0;
//默认fa记录节点数量是最多的;
if (u->size[fa] < u->size[fb]) swap(fa, fb);
u->father[fb] = fa;
u->size[fa] += u->size[fb];
return 1;
}
x
//按秩优化
typedef struct UnionSet {
int *father, *size;
int n;
} UnionSet;
UnionSet *init(int n) {
UnionSet *u = (UnionSet *)malloc(sizeof(UnionSet));
u->father = (int *)malloc(sizeof(int) * (n + 1));
u->size = (int *)malloc(sizeof(int) * (n + 1)); // 记录每棵树的节点个数
for (int i = 1; i <= n; i++) {
u->father[i] = i; //自己为一棵树
u->size[i] = 1; // 只有自己一个节点
}
u->n = n;
return u;
}
int find(UnionSet *u, int x) { //路径压缩
return x == u->father[x] ? u->father[x] : (u->father[x] = find(u, u->father[x]));
}
int merge(UnionSet *u, int a, int b) {
int fa = find(u, a), fb = find(u, b);
if (fa == fb) return 0;
//默认fa记录节点数量是最多的;
if (u->size[fa] < u->size[fb]) swap(fa, fb);
u->father[fb] = fa;
u->size[fa] += u->size[fb];
// u->father[fa] = fb;
// for (int i = 1; i <= u->n; i++) {
// if (u->father[i] != fa) continue;
// u->father[i] = fb;
// }
return 1;
}
void clear(UnionSet *u) {
if (u == NULL) return ;
free(u->father);
free(u);
return ;
}
int main() {
return 0;
}
Leetcode 128 | Leetcode 130 |
---|---|
Leetcode 200 | Leetcode 547 |
Leetcode 684 | Leetcode 685 |