题解 | 小红开宝箱

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;
int n;
vector<int>a[N];
bool v[N];
int dp[N];
int dfs(int x)
{
    for(auto& it:a[x])
    {
        if(!v[it])
        {
            v[it]=true;
            if(dp[it]==0||dfs(dp[it]))
            {
                dp[it]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int k;
        cin>>k;
        for(int j=1;j<=k;j++)
        {
            int x;
            cin>>x;
            a[i].push_back(x);
        }
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        memset(v,0,sizeof(v));
        if(dfs(i))
        {
            cnt++;
        }
    }
    if(cnt!=n)
    {
        cout<<"kou is angry";
        return 0;
    }
    int m[N];
    for(int i=1;i<=n;i++)
    {
        m[dp[i]]=i;
    }
    for(int i=1;i<=n;i++)
    {
        cout<<m[i]<<' ';
    }
    return 0;
}