题解 | 连通图

#include <iostream>
using namespace std;

const int N = 1010;
int p[N];
int find(int x) {
    if (p[x] != x)p[x] = find(p[x]);
    return p[x];
}
int main() {
    int n, m;
    while (cin >> n >> m) {
        if (n == 0 && m == 0)break;
        //并查集初始化
        for (int i = 1; i <= n; i++)
            p[i] = i;

        int x, y;
        while (m--) {
            cin >> x >> y;
            //合并边
            if (find(x) != find(y))p[find(x)] = find(y);
            }
        
        //合并完后看有几个根结点
        int count = 0;
        int root = 0;
        for (int i = 1; i <= n; i++) {
            if (root != find(i))count++, root = find(i);
        }
        if (count == 1)puts("YES");
        else puts("NO");
    }
}
// 64 位输出请用 printf("%lld")