题解 | 2024_冰阔落_1716并查集

#include<iostream>
#include<vector>

using namespace std;
vector<int> parents;

int find(int x) {
    return x == parents[x] ? x : parents[x] = find(parents[x]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    while (cin >> n >> m) {
        parents.resize(n + 1);
        for (int i = 1; i <= n; i++) parents[i] = i;
        while (m--) {
            int x, y;
            cin >> x >> y;
            if (find(x) == find(y)) cout << "Yes" << endl;
            else {
                parents[find(y)] = find(x);
                cout << "No" << endl;
            }
        }
        int count = 0;
        for (int i = 1; i <= n; i++) if (parents[i] == i) count++;
        cout << count << endl;
        for (int i = 1; i <= n; i++) if (parents[i] == i) cout << i << ' ';
        cout << '\n';
    }
    return 0;
}