| 相关算法 | 合并的时间复杂度 | 查找的时间复杂度 |
|---|---|---|
| Quick-Find算法 | O(N) | O(1) |
| Quick-Union算法 | O(lgN)~O(N) | O(lgN)~O(N) |
| Weighted按质优化 | O(lgN) | O(lgN) |
| 路径压缩 | ≈O(1) | ≈O(1) |
在实际工程中，可直接跳过按质优化采用路径压缩，时间效率上相差不大，但可以节省存储节点个数 (weight) 的内存消耗
Quick-Find
#include <stdio.h>
#include <stdlib.h>
typedef struct UnionSet {
int *flag;
int n;
} UnionSet;
UnionSet *init(int n) {
UnionSet *set = (UnionSet *)malloc(sizeof(UnionSet));
set->flag = (int *)malloc(sizeof(int) * (n + 1)); //编号一般从1开始
for (int i = 1; i <= n; i++) {
set->flag[i] = i;
}
set->n = n;
return set;
}
void clear(UnionSet *set) {
if (set == NULL) return;
free(set->flag);
free(set);
return;
}
int find(UnionSet *set, int a) {
return set->flag[a];
}
int merge(UnionSet *set, int a, int b) {
if (find(set, a) == find(set, b)) return 0;
int flag_b = set->flag[b];
for (int i = 1; i <= set->n; i++) {
if (set->flag[i] == flag_b) set->flag[i] = set->flag[a];
}
return 1;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
UnionSet *set = init(n);
for (int i = 0; i < m; i++) {
int op, a, b;
scanf("%d%d%d", &op, &a, &b);
switch (op) {
case 1:
merge(set, a, b);
break;
case 2:
printf("%s\n", find(set, a) == find(set, b) ? "YES" : "NO");
break;
}
}
clear(set);
return 0;
}
Quick-Union
#include <stdio.h>
#include <stdlib.h>
typedef struct UnionSet {
int *flag; //记录父节点的编号
int n;
} UnionSet;
UnionSet *init(int n) {
UnionSet *set = (UnionSet *)malloc(sizeof(UnionSet));
set->flag = (int *)malloc(sizeof(int) * (n + 1)); //编号一般从1开始
for (int i = 1; i <= n; i++) {
set->flag[i] = i;
}
set->n = n;
return set;
}
void clear(UnionSet *set) {
if (set == NULL) return;
free(set->flag);
free(set);
return;
}
int find(UnionSet *set, int a) {
if (set->flag[a] == a) return a;
return find(set, set->flag[a]);
//return set->flag[a] = find(set, set->flag[a]); //路径压缩
}
int merge(UnionSet *set, int a, int b) {
int flag_a = find(set, a);
int flag_b = find(set, b);
if (flag_a == flag_b) return 0;
set->flag[flag_b] = flag_a;
return 1;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
UnionSet *set = init(n);
for (int i = 0; i < m; i++) {
int op, a, b;
scanf("%d%d%d", &op, &a, &b);
switch (op) {
case 1:
merge(set, a, b);
break;
case 2:
printf("%s\n", find(set, a) == find(set, b) ? "YES" : "NO");
break;
}
}
clear(set);
return 0;
}
Weighted Quick-Union
#include <stdio.h>
#include <stdlib.h>
#define swap(a, b) { \
__typeof(a) __temp = a; \
a = b, b = __temp; \
}
typedef struct UnionSet {
int *flag; //记录父节点的编号
int *node_num; //记录子集（包括自身）的节点数量
int n;
} UnionSet;
UnionSet *init(int n) {
UnionSet *set = (UnionSet *)malloc(sizeof(UnionSet));
set->flag = (int *)malloc(sizeof(int) * (n + 1)); //编号一般从1开始
set->node_num = (int *)malloc(sizeof(int) * (n + 1));
for (int i = 1; i <= n; i++) {
set->flag[i] = i;
set->node_num[i] = 1;
}
set->n = n;
return set;
}
void clear(UnionSet *set) {
if (set == NULL) return;
free(set->flag);
free(set);
return;
}
int find(UnionSet *set, int a) {
if (set->flag[a] == a) return a;
return find(set, set->flag[a]);
//return set->flag[a] = find(set, set->flag[a]); //路径压缩
}
int merge(UnionSet *set, int a, int b) {
int fa = find(set, a);
int fb = find(set, b);
if (fa == fb) return 0;
if (set->node_num[fb] > set->node_num[fa]) swap(fa, fb);
set->flag[fb] = fa;
set->node_num[fa] += set->node_num[fb];
return 1;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
UnionSet *set = init(n);
for (int i = 0; i < m; i++) {
int op, a, b;
scanf("%d%d%d", &op, &a, &b);
switch (op) {
case 1:
merge(set, a, b);
break;
case 2:
printf("%s\n", find(set, a) == find(set, b) ? "YES" : "NO");
break;
}
}
clear(set);
return 0;
}
可采用OJ上第71题的“朋友圈”进行测试
标签：set,return,int,查集,flag,UnionSet,find,森林 From： https://www.cnblogs.com/Kelvin-Wu/p/16795309.html