此题就是求最大匹配。不过需要判断是否构成二分图。判断的方法是人选一点标记为红色（0），与它相邻的点标记为黑色（1），产生矛盾就无法构成二分图。声明一个vis[]，初始化为-1。通过深搜，相邻的点不满足异或关系就结束。如果没被标记，就标记为相邻点的异或。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=,INF=0x3f3f3f3f;
int bmap[N][N],cx[N],cy[N],dx[N],dy[N];
bool bmask[N];
int flag,vis[N];
int nx,ny,dis,ans;
bool searchpath()
{
queue<int> q;
dis=INF;
memset(dx,-,sizeof(dx));
memset(dy,-,sizeof(dy));
for(int i=;i<=nx;i++)
{
if(cx[i]==-){ q.push(i); dx[i]=; }
while(!q.empty())
{
int u=q.front(); q.pop();
if(dx[u]>dis) break;
for(int v=;v<=ny;v++)
{
if(bmap[u][v]&&dy[v]==-)
{
dy[v]= dx[u] + ;
if(cy[v]==-) dis=dy[v];
else
{
dx[cy[v]]= dy[v]+;
q.push(cy[v]);
}
}
}
}
}
return dis!=INF;
}
int findpath(int u)
{
for(int v=;v<=ny;v++)
{
if(!bmask[v]&&bmap[u][v]&&dy[v]==dx[u]+)
{
bmask[v]=;
if(cy[v]!=-&&dy[v]==dis) continue;
if(cy[v]==-||findpath(cy[v]))
{
cy[v]=u; cx[u]=v;
return ;
}
}
}
return ;
}
void maxmatch()
{
ans=;
memset(cx,-,sizeof(cx));
memset(cy,-,sizeof(cy));
while(searchpath())
{
memset(bmask,,sizeof(bmask));
for(int i=;i<=nx;i++)
if(cx[i]==-) ans+=findpath(i);
}
}
void init()
{
memset(bmap,,sizeof(bmap));
}
void dfs(int u)
{
for(int i=;i<=nx&&!flag;i++)
{
if(u==i) continue;
if(bmap[u][i]){
if(vis[i]!=-&&(vis[u]^vis[i]!=)) flag=;
if(vis[i]==-) {vis[i]=vis[u] ^;dfs(i);}
}
}
}
int main()
{
//freopen("test.txt","r",stdin);
int cas,i,j,k,m,n;
while(scanf("%d%d",&n,&m)!= EOF)
{
init();
memset(vis,-,sizeof(vis));
flag=;
for(i=;i<=m;i++)
{
scanf("%d%d",&j,&k);
bmap[j][k]=;
}
nx=ny=n;
vis[]=;
dfs();
if(flag) {printf("No\n");continue;}
maxmatch();
printf("%d\n",ans);
}
return ;
}