Cindy Homework

    1#include <bits/stdc++.h>
    2 
    3using namespace std;
    4 
    5struct DSU {
    6    vector<int> parent;   
    7    vector<int> rank;      
    8 
    9    DSU(int n) : parent(n + 1), rank(n + 1, 0) {
    10        iota(parent.begin(), parent.end(), 0);  // parent[i] = i
    11    }
    12 
    13    int find(int x) {                      
    14        return parent[x] == x ? x : parent[x] = find(parent[x]);
    15    }
    16 
    17    void unite(int x, int y) {              
    18        int rootX = find(x);
    19        int rootY = find(y);
    20        if (rootX == rootY) return;      
    21 
    22        if (rank[rootX] > rank[rootY]) {    
    23            parent[rootY] = rootX;
    24        } else if (rank[rootX] < rank[rootY]) {
    25            parent[rootX] = rootY;
    26        } else {                            
    27            parent[rootY] = rootX;
    28            rank[rootX]++;                 
    29        }
    30    }
    31};
    32 
    33int main() {
    34    ios::sync_with_stdio(false);
    35    cin.tie(nullptr);
    36 
    37    int n, m; // n = people, m = classes
    38    cin >> n >> m;
    39 
    40    DSU dsu(n);
    41 
    42    for (int i = 0; i < m; i++) {
    43        int k; cin >> k;                  
    44        int first;
    45        cin >> first;  // representative student
    46        for (int i = 1; i < k; i++) {       // union with the rest
    47            int x; 
    48            cin >> x;
    49            dsu.unite(first, x);
    50        }
    51    }
    52    //person one is by default infected 
    53    vector<int> infected;
    54    int person = dsu.find(1);
    55    for (int i = 1; i <= n; ++i){
    56        if (dsu.find(i) == person){
    57        infected.push_back(i);
    58    }
    59  }
    60    cout << infected.size() << '\n';
    61    for (int i = 0; i < infected.size(); i++)
    62        cout << infected[i] << (i + 1 == infected.size() ? '\n' : ' ');
    63    return 0;
    64}
    65