题意：有两两认识的一些同学，但是a认识b，b认识c，不代表a认识c，求这个关系能否构成二分图，以及最大匹配
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxe = 4e4 + 50,maxn = 250;
struct node
{
int to,next;
node(){}
node(int a,int b){to = a ; next = b;}
}edge[maxe << 1];
int h[maxn],col[maxn],belong[maxn],used[maxn];
int edgenum = 0;
void init()
{
edgenum = 0;
for(int i = 0; i < maxn; i++) col[i] = h[i] = -1,belong[i] = used[i] = 0;
}
void add(int t,int f)
{
edge[edgenum] = node(t,h[f]);
h[f] = edgenum++;
}
bool colour(int u)
{
int now = !col[u];
for(int i = h[u]; ~i; i = edge[i].next)
{
int v = edge[i].to;
if(col[v] == -1)
{
col[v] = now;
if(colour(v) == 0) return false;
}
else if(col[v] == col[u])
return false;
}
return true;
}
bool Find(int u)
{
for(int i = h[u]; ~i ; i = edge[i].next)
{
int v = edge[i].to;
if(used[v] == 1) continue;
used[v] = 1;
if(!belong[v] || Find(belong[v]))
{
belong[v] = u;
return true;
}
}
return false;
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
int a,b;
init();
for(int i = 0; i < m ; i++)
{
scanf("%d%d",&a,&b);
add(a,b); add(b,a);
}
int flag = 0;
for(int u = 1; u <= n ; u++)
{
if(col[u] != -1) continue;
col[u] = 1;
if(colour(u) == 0) {flag = 1;break;}
}
if(flag) printf("No\n");
else
{
int ans = 0;
for(int i = 1; i <= n; i++)
{
memset(used,0,sizeof(used));
if(col[i] == 1) continue;
if(Find(i)) ans++;
}
printf("%d\n",ans);
}
}
return 0;
}