学步园

#include <iostream><br /> #include <vector><br /> using namespace std;<br /> #define MAX 1005</p> <p>vector< vector<int> > map;<br /> int mark[MAX];<br /> bool flag[MAX];<br /> int nm,num;</p> <p>bool dfs(int pos) //搜pos点是否存在增广路<br /> {<br /> int i,pre,tp;<br /> int len=map[pos].size();<br /> for(i=0;i<len;i++)<br /> {<br /> tp=map[pos][i];<br /> if(!flag[tp])<br /> {<br /> flag[tp]=true;<br /> pre=mark[tp];<br /> mark[tp]=pos;<br /> if(pre==-1 || dfs(pre)) return true; //如果没被访问过或者存在增广路，pos到该点就存在增广路<br /> mark[tp]=pre; //否则pos到该点就不存在增广路<br /> }<br /> }<br /> return false;<br /> }</p> <p>int main()<br /> {<br /> int n,m,t,i; //n是v1集合的节点数（男孩的人数）m是v2集合的节点数（女孩的人数）t是有t对之间存在边（即有关系）<br /> while (scanf("%d%d%d",&n,&m,&t),n)<br /> {<br /> num=0;<br /> nm=n+m;<br /> map.clear();<br /> map.resize(nm+10);<br /> memset(mark,-1,sizeof(mark));<br /> int x,y;<br /> while (t--)<br /> {<br /> scanf("%d%d",&x,&y);<br /> y+=n;<br /> map[x].push_back(y);<br /> }<br /> for (i=1;i<=n;i++)<br /> {<br /> memset(flag,0,sizeof(flag));<br /> if(dfs(i)) num++;<br /> }<br /> printf("%d/n",num);<br /> }<br /> return 0;<br /> }