匈牙利算法(二分图匹配 O(VE))

牛客每日一题https://www.nowcoder.com/practice/f51fb4a38a464b1c86d0a0adf1920d65?channelPut=tracker2

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

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    vector<vector<int>> adj(n+1);
    for(int i=1;i<=n;i++){
        int k;cin>>k;
        for(int j=1;j<=k;j++){
            int x;cin>>x;
            adj[x].push_back(i);
        }
    }
    vector<int> mark(n+1,-1);
    vector<bool> vis(n+1,false);
    auto dfs=[&](auto&& self,int u)->bool {
        for(auto v:adj[u]){
            if(vis[v]) continue;
            vis[v]=true;
            if(mark[v]==-1||self(self,mark[v])){
                mark[v]=u;
                return true;
            }
        }
        return false;
    };
    int ans=0;
    for(int i=1;i<=n;i++){
        vis.assign(n+1, false);
        if(dfs(dfs,i)) ans++;
    }
    if(ans!=n){
        cout<<"kou is angry";
        return 0;
    }
    for(int i=1;i<=n;i++){
        cout<<mark[i]<<" ";
    }
}
// 64 位输出请用 printf("%lld")

左匹配右，如果右侧没有匹配或者右侧之前匹配的这个能找到新的，就匹配当前的这个右。