用c++写一个并查集的代码

### 回答1：

我可以给你一个使用 C 语言实现并查集的代码示例：#include <stdio.h>
#define MAX_SIZE 100

// 数组实现并查集的根节点
int parent[MAX_SIZE];

// 初始化
void init(int n)
{
for (int i = 0; i < n; i++)
parent[i] = i;
}

// 查找根节点
int find(int x)
{
int x_root = x;
while (parent[x_root] != x_root)
x_root = parent[x_root];
return x_root;
}

// 合并
void Union(int x, int y)
{
int x_root = find(x);
int y_root = find(y);
parent[x_root] = y_root;
}

### 回答2：
并查集是一种用于解决并查集问题的数据结构，它主要用于处理集合的合并与查询操作。下面是一个用C语言实现的并查集代码：

#include <stdio.h>
#include <stdlib.h>

// 定义并查集数据结构
typedef struct {
    int *parent;
    int *rank;
    int size;
} UnionFind;

// 初始化并查集
void init(UnionFind *uf, int size) {
    uf->parent = (int *) malloc(sizeof(int) * size);
    uf->rank = (int *) malloc(sizeof(int) * size);
    uf->size = size;
    
    for (int i = 0; i < size; i++) {
        uf->parent[i] = i;  // 初始化每个节点的父节点为自身
        uf->rank[i] = 0;  // 初始化每个节点的秩为0
    }
}

// 查找根节点（路径压缩）
int findRoot(UnionFind *uf, int node) {
    if (uf->parent[node] != node) {
        uf->parent[node] = findRoot(uf, uf->parent[node]);
    }
    return uf->parent[node];
}

// 合并两个集合（按秩合并）
void unionSets(UnionFind *uf, int node1, int node2) {
    int root1 = findRoot(uf, node1);
    int root2 = findRoot(uf, node2);
    
    if (root1 == root2) return;
    
    if (uf->rank[root1] < uf->rank[root2]) {
        uf->parent[root1] = root2;
    } else if (uf->rank[root1] > uf->rank[root2]) {
        uf->parent[root2] = root1;
    } else {
        uf->parent[root2] = root1;
        uf->rank[root1]++;
    }
}

int main() {
    int n = 5;  // 假设有5个节点
    UnionFind uf;
    
    init(&uf, n);
    
    // 合并集合
    unionSets(&uf, 0, 1);
    unionSets(&uf, 2, 3);
    unionSets(&uf, 0, 4);
    unionSets(&uf, 3, 4);
    
    // 查询根节点
    printf("节点0的根节点：%d\n", findRoot(&uf, 0));
    printf("节点1的根节点：%d\n", findRoot(&uf, 1));
    printf("节点2的根节点：%d\n", findRoot(&uf, 2));
    printf("节点3的根节点：%d\n", findRoot(&uf, 3));
    printf("节点4的根节点：%d\n", findRoot(&uf, 4));
    
    free(uf.parent);
    free(uf.rank);
    return 0;
}

此代码中，定义了并查集的数据结构UnionFind，其中包含了parent数组用于存储每个节点的父节点，rank数组用于存储每个节点的秩，size表示节点的个数。init函数用于初始化并查集，findRoot函数用于查找节点的根节点并进行路径压缩优化，unionSets函数用于合并两个集合并进行按秩合并优化。在main函数中，首先通过init函数初始化并查集，然后通过unionSets函数合并集合，并通过findRoot函数查询节点的根节点。最后，记得释放动态分配的内存。

### 回答3：
以下是一个使用C语言编写的并查集代码示例：

#include <stdio.h>

// 定义并查集节点结构
typedef struct {
    int parent; // 节点的父节点
    int rank; // 节点的秩
} UnionFindNode;

// 初始化并查集
void initialize(UnionFindNode *nodes, int size) {
    for (int i = 0; i < size; i++) {
        nodes[i].parent = i;
        nodes[i].rank = 0;
    }
}

// 查找节点所属的集合根节点
int findRoot(UnionFindNode *nodes, int node) {
    if (nodes[node].parent != node) {
        // 路径压缩：将节点直接链接到根节点，减少后续查找的时间复杂度
        nodes[node].parent = findRoot(nodes, nodes[node].parent);
    }
    return nodes[node].parent;
}

// 合并两个集合
void unionSets(UnionFindNode *nodes, int node1, int node2) {
    int root1 = findRoot(nodes, node1);
    int root2 = findRoot(nodes, node2);
    
    if (root1 != root2) {
        // 按秩合并：将秩较小的根节点指向秩较大的根节点，减少树的高度
        if (nodes[root1].rank < nodes[root2].rank) {
            nodes[root1].parent = root2;
        } else if (nodes[root1].rank > nodes[root2].rank) {
            nodes[root2].parent = root1;
        } else {
            nodes[root2].parent = root1;
            nodes[root1].rank++;
        }
    }
}

int main() {
    int size = 10; // 并查集的节点个数
    UnionFindNode nodes[size];
    
    initialize(nodes, size);
    
    unionSets(nodes, 1, 2);
    unionSets(nodes, 3, 4);
    unionSets(nodes, 5, 6);
    
    printf("%d\n", findRoot(nodes, 2)); // 输出2所在集合的根节点
    
    unionSets(nodes, 1, 4);
    
    printf("%d\n", findRoot(nodes, 2)); // 输出2所在集合的根节点
    
    return 0;
}

这段代码实现了并查集的基本功能，包括初始化并查集、查找节点所属的集合根节点以及合并两个集合。使用路径压缩和按秩合并的策略，可以有效提高查找和合并操作的效率。在示例代码的测试部分，我们先合并了节点1和2，节点3和4，节点5和6，然后输出了节点2所在集合的根节点，接着将节点1和4合并，再次输出节点2所在集合的根节点，以演示并查集的使用过程。