问题描述 给定并查集的数据类型如下 typedef struct { int * parent; int size; }SNode,* Set; 请设计int findSet(Set S,int x)函数。 该函数查找节点x的根节点，并返回根节点编号。 在查找过程中同时压缩路径。 其中根节点的parent为-1. 请注意，本题有预置代码，只需提交所要求的函数定义代码即可。 预置代码 #include<bits/stdc++.h> using namespace std; typedef int ElementType; typedef struct { int * parent; int size; }SNode,* Set; int findSet(Set S,int x); int main() { /*此处代码由测试程序自动添加，主要为了向顺序表中插入数据 并输出数据,你无需关心此处代码的具体实现细节。 如果有必要，请自己添加代码以测试你的函数是否正确。 */ return 0; } /*你的提交的代码将被添加在此处，请完成题目所要求的函数的定义*/ c语言代码

int findSet(Set S, int x) {
if (S->parent[x] == -1) {
return x;
}
S->parent[x] = findSet(S, S->parent[x]); // 路径压缩
return S->parent[x];
}

相关问题

问题描述 给定并查集的数据类型如下 typedef struct { int * parent; int size; }SNode,* Set; 请设计void unionSet(Set S,int x,int y)函数。 该函数将x和y所在的两个集合(子树)合并。 请注意，本题有预置代码，只需提交所要求的函数定义代码即可。 预置代码 #include<bits/stdc++.h> using namespace std; typedef int ElementType; typedef struct { int * parent; int size; }SNode,* Set; void unionSet(Set S,int x,int y); int main() { /*此处代码由测试程序自动添加，主要为了向顺序表中插入数据 并输出数据,你无需关心此处代码的具体实现细节。 如果有必要，请自己添加代码以测试你的函数是否正确。 */ return 0; } /*你的提交的代码将被添加在此处，请完成题目所要求的函数的定义*/ c语言代码

void unionSet(Set S, int x, int y) {
int rootX = find(S, x);
int rootY = find(S, y);
if (rootX != rootY) {
if (S->parent[rootX] < S->parent[rootY]) {
S->parent[rootX] += S->parent[rootY];
S->parent[rootY] = rootX;
} else {
S->parent[rootY] += S->parent[rootX];
S->parent[rootX] = rootY;
}
S->size--;
}
}

int find(Set S, int x) {
if (S->parent[x] < 0) {
return x;
} else {
return S->parent[x] = find(S, S->parent[x]);
}
}