AcWing
1394. 完美牛棚
匈牙利算法。使用邻接矩阵g[N][N]记录二分图的边，读取时只需要读从左半部到右半部的有向边即可。match[N]用来记录右半部的匹配情况(是否已经匹配)。visited[N]用来记录左半部的单次迭代中，右半部中的点是否访问过。对于每次左半部点的迭代i，更新visited[N]数组，对于每个右半部的点j，如果j没被访问，并且可以与i配对，那么将i标记为访问，如果j尚未配对，或者与j配对的点可以与右半部其他点配对，那么将i与j配对(在递归中将之前与j配对的左半部点跟右半部的另一点配对)。如果使用邻接矩阵存储图，算法的时间复杂度为$O(V^3)$；如果使用邻接表存储图，算法的时间复杂度为$O(VE)$.
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 410;
int g[N][N], match[N];
bool visited[N];
bool find(int x){
for(int i = 1; i <= m; i++){
if(!visited[i] && g[x][i]){
visited[i] = true;
if(!match[i] || find(match[i])){
match[i] = x;
return true;
}
}
}
return false;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++){
int s;
cin >> s;
while(s--){
int id;
cin >> id;
g[i][id] = 1;
}
}
int res = 0;
for(int i = 1; i <= n; i++){
memset(visited, false, sizeof visited);
if(find(i)) res++;
}
cout << res << endl;
return 0;
}