题解 | 小红开宝箱

#include<bits/stdc++.h>
#define pii pair<int,int>

using namespace std;

const int N = 1e5+5;

int n;
int cnt[N], ans[N];

vector<int> v[N], bel[N];
set<pii> S;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>cnt[i];
        for(int j=1;j<=cnt[i];j++){
            int x;
            cin>>x;
            v[x].push_back(i);
            bel[i].push_back(x);
        }
    }
    for(int i=1;i<=n;i++) S.insert({v[i].size(), i});
    while(S.size() > 0){
        auto it = S.begin();
        S.erase(it);
        int now = it->second;
        bool flag = false;
        int res = 0;
        for(int i:v[now]){
            if(ans[i]) continue;
            res = i;
            ans[i] = now;
            flag = true;
            break;
        }
        if(!flag){
            cout<<"kou is angry";
            return 0;
        }
        for(int j:bel[res]){
            auto it = S.find({v[j].size(),j});
            if(it == S.end()) continue;
            S.erase(it);
            vector<int> nw;
            for(int k:v[j]) if(k != res) nw.push_back(k);
            v[j] = nw;
            S.insert({v[j].size(), j});
        }
    }
    for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
    return 0;
}