1 条题解

  • 0
    @ 2026-3-16 20:27:40
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    int findfa(vector<int>& fa, int x) {
        if (fa[x] == x) return x;
        return fa[x] = findfa(fa, fa[x]);
    }
    
    void mergefa(vector<int>& fa, int a, int b) {
        a = findfa(fa, a);
        b = findfa(fa, b);
        if (a != b) fa[b] = a;
    }
    
    int main() {
        int n, m;
        cin >> n >> m;
    
        vector<int> fa(m + 1);
        for (int i = 1; i <= m; i++) fa[i] = i;
    
        for (int i = 0; i < n; i++) {
            int k;
            cin >> k;
    
            int first, wzpjsylai;
            cin >> first;
            for (int j = 1; j < k; j++) {
                cin >> wzpjsylai;
                mergefa(fa, first, wzpjsylai);
            }
        }
    
        // 先路径压缩
        for (int i = 1; i <= m; i++) {
            fa[i] = findfa(fa, i);
        }
    
        const int INF = 1e9;
        vector<int> mn(m + 1, INF);
    
        // 统计每个连通块最小值
        for (int i = 1; i <= m; i++) {
            mn[fa[i]] = min(mn[fa[i]], i);
        }
    
        vector<int> ans;
        for (int i = 1; i <= m; i++) {
            if (mn[i] != INF) ans.push_back(mn[i]);
        }
    
        sort(ans.begin(), ans.end());
    
        for (int i = 0; i < (int)ans.size(); i++) {
            if (i) cout << ' ';
            cout << ans[i];
        }
        cout << '\n';
    
        return 0;
    }
    
    • 1

    信息

    ID
    195
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    (无)
    递交数
    24
    已通过
    5
    上传者