题解 | #连通图#

并查集

#include <iostream>
#include <vector>
using namespace std;

void Initial(vector<int>& s) {
    for (int i = 1; i < s.size(); i++) {
        s[i] = -1;
    }
}

int Find(vector<int>& s, int x) {
    int root = x;
    while (s[root] >= 0) {
        root = s[root];
    }
    while (x != root) {
        int t = s[x];
        s[x] = root;
        x = t;
    }
    return root;
}

void Union(vector<int>& s, int a, int b) {
    int roota = Find(s, a);
    int rootb = Find(s, b);
    if (roota == rootb) return;
    if (s[roota] <= s[rootb]) {
        s[roota] += s[rootb];
        s[rootb] = roota;
    }
    else {
        s[rootb] += s[roota];
        s[roota] = rootb;
    }
}

int main() 
{
    int n, m;
    while (cin >> n) {
        cin >> m;
        if (n == 0 && m == 0) break;
        vector<int> s(n+1, 0);
        Initial(s);
        while (m--) {
            int a, b;
            cin >> a >> b;
            Union(s, a, b);
        }
        int result = 0;
        for(int i = 1; i < s.size(); i++) {
            if (s[i] <= 0) {
                result++;
            }
        }
        if (result > 1) cout << "NO" << endl;
        else cout << "YES" << endl;
    }
    return 0;
}