//算法核心是求最大匹配数 #include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string.h> #define maxint 999999999 using namespace std; int cx[1005],cy[1005],edge[1005][1005]; int cx[1005]; int cy[1005]; int edge[1005][1005];//用二位数组实现邻接矩阵表示二分图的左右存在的关系，edge[i][j]表示二分图左i和右j是否存在关系，1表示存在，0表示不存在 bool vis[1005];//记录图右点是否被访问 int n,nx,ny;//nx表示图左可匹配数，ny是图右的可匹配数 int path(int u) { for(int i=1;i<=ny;i++) { if(edge[u][i]&&!vis[i])//是否u与i存在可匹配关系且点右i未被标记 { vis[i]=1; if(cy[i]==-1||path(cy[i]))//cy[i]节点本身未被访问或cy[i]节点之后存在未被访问的点 { cy[i]=u; //左右匹配 cx[u]=i; return 1; //最大匹配数+1 } } } return 0;//若不存在可匹配的则返回0 } int match() { memset(cx,-1,sizeof(cx));//约定用-1表示节点未被访问 memset(cy,-1,sizeof(cy)); int res=0;//记录最大匹配数 for(int i=1;i<=nx;i++) { if(cx[i]==-1) { memset(vis,0,sizeof(vis)); //每次进入匹配需初始化标记 res+=path(i); } } return res; } int main() { int x,y; while(scanf("%d",&n)==1&&n) { scanf("%d %d",&nx,&ny); memset(edge,0,sizeof(edge)); while(n--) { scanf("%d %d",&x,&y); edge[x][y]=1; } int sum=match(); printf("%d ",sum); }return 0; } //明天再把bfs的写法理解一下。。