题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=2444
题意：有n个学生，有m对人是认识的，每一对认识的人能分到一间房，问能否把n个学生分成两部分，每部分内的学生互不认识，而两部分之间的学生认识。如果可以分成两部分，就算出房间最多需要多少间，否则就输出No。
首先判断是否为二分图，然后判断最大匹配
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int maxn = 205;
int head[maxn], vis[maxn], matching[maxn];
bool check[maxn];
int eid;
struct Edge
{int u, v, nxt;Edge(){}Edge(int from, int to, int nx):u(from), v(to), nxt(nx){}
}edge[maxn*maxn];
inline void AddEdge(int u, int v)
{edge[eid] = Edge(u, v, head[u]);head[u] = eid++;edge[eid] = Edge(v, u, head[v]);head[v] = eid++;
}
bool judge(int n)
{memset(vis, -1, sizeof(vis));queue<int> q;for(int i = 1; i <= n; i++){if(vis[i] == -1){q.push(i);vis[i] = 1;while(!q.empty()){int u = q.front();q.pop();for(int j = head[u]; j != -1; j = edge[j].nxt){int v = edge[j].v;if(vis[v] == -1){vis[v] = !vis[u];q.push(v);}else if(vis[v] == vis[u])return false;}}}}return true;
}
bool dfs(int u)
{for(int i = head[u]; i != -1; i = edge[i].nxt){int v = edge[i].v;if(!check[v]){check[v] = true;if(matching[v] == -1 || dfs(matching[v])){matching[u] = v;matching[v] = u;return true;}}}return false;
}
int hungarian(int n)
{int ans = 0;memset(matching, -1, sizeof(matching));for(int i = 1; i <= n; i++){if(matching[i] == -1){memset(check, false, sizeof(check));if(dfs(i))ans++;}}return ans;
}
int main()
{int n, m;while(scanf("%d%d", &n, &m) != EOF){eid = 0;memset(head, -1, sizeof(head));for(int i = 0; i < m; i++){int u, v;scanf("%d%d", &u, &v);AddEdge(u, v);}if(judge(n))printf("%d\n", hungarian(n));elseprintf("No\n");}return 0;
}