题解 | #星际航线规划#

/*这段C代码使用了并查集（Union-Find）算法来判断给定的星球之间的航线是否存在环路。下面是代码的解释：

1.  首先定义了一个大小为MAX\_PLANETS的parent数组，用来存储每个星球的父节点。
2.  定义了find函数，用来找到某个星球的根节点（即所属集合的代表元素）。
3.  定义了unite函数，用来将两个星球所在的集合合并。
4.  在主函数main中，首先读入星球的数量n和航线的数量m。
5.  初始化每个星球的父节点为自身，即每个星球单独构成一个集合。
6.  依次读入每条航线的起点x和终点y，判断它们是否在同一个集合中：
    *   如果不在同一个集合中，则将它们合并。
    *   如果在同一个集合中，说明存在环路，输出"No"并结束程序。
7.  如果所有航线都被处理完毕后仍未输出"No"，则说明不存在环路，输出"Yes"。

这段代码利用并查集的特性，通过不断合并集合的方式来判断是否存在环路，从而判断是否能够访问所有的星球。*/
#include <stdio.h>

#define MAX_PLANETS 10001

int parent[MAX_PLANETS];

int find(int x) {
    if (parent[x] == x) {
        return x;
    }
    return parent[x] = find(parent[x]);
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        parent[y] = x;
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }

    int x, y;
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &x, &y);
        if (find(x) != find(y)) {
            unite(x, y);
        } else {
            printf("No\n");
            return 0;
        }
    }

    printf("Yes");
    return 0;
}