2033: 网络互通（C语言）并查集

解题思路:

注意事项:

参考代码:

#include <stdio.h>
#include <string.h>

// 初始化并查集
int *InitUFS(int size) {
    int *ufs = (int *) malloc(sizeof(int) * (size + 1));
    for (int i = 0; i <= size; i++) {                    // 初始化并查集，每个结点的父结点都是它本身
        ufs[i] = i;
    }
    return ufs;
}

// 查找 x 所在集合的根结点
int FindRoot(int *ufs, int x) {
    for (; x >= 0 && x != ufs[x]; x = ufs[x]);           // 从x往上查找其所在集合的根结点
    return x;
}

// 将 x, y 所在的两个集合合并
void UnionSets(int *ufs, int x, int y) {
    ufs[FindRoot(ufs, y)] = FindRoot(ufs, x);           // 找到 y 的根结点，将其合并到 x 的根结点的子集
}

int main() {
    int n, m, xi, yi, x, y, *ufs;
    scanf("%d %d", &n, &m);
    ufs = InitUFS(n);
    while (m--) {
        scanf("%d %d", &xi, &yi);
        UnionSets(ufs, xi, yi);
    }
    scanf("%d %d", &x, &y);
    int root1 = FindRoot(ufs, x);
    int root2 = FindRoot(ufs, y);
    printf(root1 == root2 ? "Yes\n" : "No\n");
    free(ufs);
    return 0;
}