基本概念
二分图：若图G<V,E>可以分成两个不相交集合A、B，则图中的任意一条边的两端分别属于这两个集合，集合内部没有边。
匹配：二分图中一个匹配是一个边的集合，这些边没有公共的交点。
匹配边：一个匹配中的边。
匹配点：匹配边的端点。
算法思想
扫描A中每个点，若E中存在边e，连接A中u与B中的v，则判断v点是否已经被匹配。若未匹配则将u、v配对；若已经匹配则为与v匹配的点w重新匹配，若成功则u也成功与v匹配；否则u匹配失败。
算法实现（POJ-1274）
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int maxn=210;
const int maxm=210;
int n,m;
vector<int> edge[maxn];
int b[maxm],used[maxm];
bool dfs(int t)
{
for(int i=0;i<edge[t].size();i++)
{
int v=edge[t][i];
if(used[v]==0)
{
used[v]=1;
if(b[v]==0||dfs(b[v]))
{
b[v]=t;
return true;
}
}
}
return false;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
memset(b,0,sizeof(b));
for(int i=0;i<=n;i++)
{
edge[i].clear();
}
int ans=0;
for(int i=1;i<=n;i++)
{
int si;
scanf("%d",&si);
for(int j=0;j<si;j++)
{
int v;
scanf("%d",&v);
edge[i].push_back(v);
}
}
for(int i=1;i<=n;i++)
{
memset(used,0,sizeof(used));
if(dfs(i))
ans++;
}
printf("%d\n",ans);
}
return 0;
}
