介绍
二分图就是一类可以将其中的节点分为两类的图，每一类节点内部之间没有边相连。
给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边...形成的路径叫交替路。
增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路（agumenting path）。
二分图匹配问题有两种解法：网络流和匈牙利算法。网络流算法即是在构图时加入一个超级源点和一个超级超级汇点，并将其中一类点进行拆点，将边的流量设为1即可。
然而对于少量二分图的匹配，有更简单的算法进行求解，就是匈牙利算法。匈牙利算法是根据增广路扩充匹配的算法。
对于任意匹配，如果我们能找到他的增广路，那么，我们使用未匹配
代码
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
using namespace std;
const int MAX_N=1100;
int first[MAX_N],second[MAX_N];
int vis[MAX_N];
vector<int> G[MAX_N];
bool findex(int s){
for(int i=0;i<G[s].size();i++){
if(vis[G[s][i]]==0){
vis[G[s][i]]=1;
if( (second[G[s][i]]==0) || (findex(second[G[s][i]]))){
second[G[s][i]]=s;
return true;
}
}
}
return false;
}
int n,m;
int main(void){
while(~scanf("%d%d",&n,&m)){
for(int i=0;i<=n;i++)
G[i].clear();
for(int i=1;i<=n;i++){
int t,a;
scanf("%d",&t);
for(int j=0;j<t;j++){
scanf("%d",&a);
G[i].push_back(a);
}
}
int ans=0;
memset(second,0,sizeof(second));
for(int i=1;i<=n;i++)
{
//memset(vis,0,sizeof(vis));
if(findex(i))
ans++;
}
//for(int i=1;i<=n;i++){
// printf("%d ",second[i]);
//}
printf("%d\n",ans);
}
return 0;
}
