C语言并查集 demo
时间: 2024-07-16 07:00:30 浏览: 73
C语言中的并查集(Disjoint Set Union,DSU)是一种数据结构,常用于解决不相交集合的问题,如图的连通性检测、找出给定元素的根节点等。它维护了一组元素,每个元素都有一个代表它的“根”或“祖先”,通过合并操作可以把两个集合合并成一个。
下面是一个简单的C语言并查集的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct DSU {
int* parent; // 存储每个元素的根索引
int size; // 每个集合的大小
} DSU;
// 初始化并查集
DSU* create_set(int n) {
DSU* dsu = (DSU*)malloc(sizeof(DSU));
dsu->parent = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
dsu->parent[i] = i;
dsu->size = n;
}
return dsu;
}
// 查找根节点(路径压缩)
int find_root(DSU* dsu, int node) {
if (dsu->parent[node] != node) {
dsu->parent[node] = find_root(dsu, dsu->parent[node]);
}
return dsu->parent[node];
}
// 合并两个集合
void union_set(DSU* dsu, int node1, int node2) {
int root1 = find_root(dsu, node1);
int root2 = find_root(dsu, node2);
// 如果根节点不同,合并它们
if (root1 != root2) {
if (dsu->size[root1] < dsu->size[root2]) {
dsu->parent[root1] = root2;
dsu->size[root2] += dsu->size[root1];
} else {
dsu->parent[root2] = root1;
dsu->size[root1] += dsu->size[root2];
}
}
}
// 主函数演示
int main() {
DSU* ds = create_set(5);
printf("Initial sets: \n");
for (int i = 0; i < 5; i++) {
printf("%d -> %d\n", i, find_root(ds, i));
}
union_set(dsu, 0, 2);
union_set(dsu, 3, 4);
printf("\nAfter merging: \n");
for (int i = 0; i < 5; i++) {
printf("%d -> %d\n", i, find_root(ds, i));
}
return 0;
}
```
这个例子中,我们首先创建了一个包含5个元素的并查集。在`main`函数中,我们展示了如何初始化并查找每个元素的根,以及如何合并两个集合。运行这个程序,你可以看到合并操作后的结果。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)