题解 | 连通图

#include <iostream>
#include <vector>

using namespace std;

int find_parent(vector<int> vec, int a)
{
    if(vec[a] == a) return a;
    else return find_parent(vec, vec[a]);
}

void union_set(vector<int> &vec, int a, int b)
{
    int ax = find_parent(vec, a);
    int bx = find_parent(vec, b);
    if(ax != bx) vec[bx] = ax;
}

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    while(cin >> n >> m)
    {
        if(n == 0 && m == 0) break;
        vector<int> vec(n + 1, 0);
        for(int i = 1; i <= n; i++) vec[i] = i;
        int a, b;
        int sum = 0;
        for(int i = 0; i < m; i++)
        {
            cin >> a >> b;
            if(find_parent(vec, a) != find_parent(vec, b))
            {
                union_set(vec, a, b);
                sum++;
            }
        }
        if(sum == n - 1) cout << "YES" << "\n";
        else cout << "NO" << "\n";
    }
    return 0;
}