【PTA数据结构 | C语言版】不相交集基本操作

本专栏持续输出数据结构题目集，欢迎订阅。

题目

请编写程序，实现不相交集的基本操作。
注意：此处假设集合元素 i 和 j 合并时，总是将 i 所在的集合并入 j 所在的集合，即合并后集合的名称为 j 所在的集合名称。

输入格式：
输入首先在第一行给出两个正整数，依次为集合中元素个数 n（1<n≤100）和元素之间的关系数 m（≤n）。
随后 m 行，每行给出一对等价元素的编号，从 1 开始。同行数字均以一个空格分隔。
接下来给出一个正整数 k（≤100），随后 k 行，每行给出一对待查询的关系，即一对元素的编号。

输出格式：
参考样例。
首先输出集合中每个元素的父结点编号，格式为 set[i] = j，表示编号为 i 的元素的父结点编号为 j。按 i 的升序输出。如果 i 没有父结点，则规定 set[i] = i。
随后对每一对待查询的关系，如果它们属于同一个等价集合，就在一行中输出 yes，否则输出 no。

输入样例：
8 5
1 4
2 3
3 5
4 2
6 7
7
1 3
4 5
5 1
2 5
6 8
4 8
3 7

输出样例：
set[1] = 4
set[2] = 3
set[3] = 5
set[4] = 5
set[5] = 5
set[6] = 7
set[7] = 7
set[8] = 8
yes
yes
yes
yes
no
no
no

代码

#include <stdio.h>
#include <stdlib.h>#define MAX_ELEMENTS 101  // 元素编号从1开始，最大100// 并查集父节点数组，parent[i]表示元素i的父节点
int parent[MAX_ELEMENTS];// 初始化并查集，每个元素的父节点为自身
void initSet(int n) {for (int i = 1; i <= n; i++) {parent[i] = i;}
}// 查找元素x所在集合的根节点（不带路径压缩）
int find(int x) {// 若x不是根节点，继续向上查找while (parent[x] != x) {x = parent[x];}return x;
}// 合并操作：将i所在的集合并入j所在的集合
void unionSets(int i, int j) {int rootI = find(i);  // 找到i的根节点int rootJ = find(j);  // 找到j的根节点// 只有当两者属于不同集合时才需要合并if (rootI != rootJ) {parent[rootI] = rootJ;  // 将i的根节点的父节点设为j的根节点}
}int main() {int n, m;scanf("%d %d", &n, &m);// 初始化并查集initSet(n);// 处理合并操作for (int i = 0; i < m; i++) {int a, b;scanf("%d %d", &a, &b);// 按照题目要求：将a所在的集合并入b所在的集合unionSets(a, b);}// 输出每个元素的父节点for (int i = 1; i <= n; i++) {printf("set[%d] = %d\n", i, parent[i]);}// 处理查询操作int k;scanf("%d", &k);for (int i = 0; i < k; i++) {int a, b;scanf("%d %d", &a, &b);// 若两个元素的根节点相同，则属于同一个集合if (find(a) == find(b)) {printf("yes\n");} else {printf("no\n");}}return 0;
}