题目来源：HDU 2444 The Accomodation of Students

题意：n个人能否够分成2组 每组的人不能相互认识 就是二分图判定 能够分成2组 每组选一个2个人认识能够去一个双人间 最多能够有几组

思路：二分图判定+最大匹配

#include <cstdio>

#include <cstring>

#include <vector>

using namespace std;

const int maxn = 550;

int vis[maxn];

int y[maxn];

vector <int> G[maxn];

int n, m;

int color[maxn];

bool bipartite(int u)

{

	for(int i = 0; i < G[u].size(); i++)

	{

		int v = G[u][i];

		if(color[u] == color[v])

			return false;

		if(!color[v])

		{

			color[v] = 3 - color[u];

			if(!bipartite(v))

				return false;

		}

	}

	return true;

}

bool dfs(int u)

{

	for(int i = 0; i < G[u].size(); i++)

	{

		int v = G[u][i];

		if(vis[v] || color[v] == 1)

			continue;

		vis[v] = true;

		if(y[v] == -1 || dfs(y[v]))

		{

			y[v] = u;

			return true;

		}

	}

	return false;

}

int match()

{

	int ans = 0;

	memset(y, -1, sizeof(y));

	for(int i = 1; i <= n; i++)

	{

		memset(vis, 0, sizeof(vis));

		if(color[i] == 1 && dfs(i))

			ans++;

	}

	return ans;

}

int main()

{

	//int T;

	//scanf("%d", &T);

	while(scanf("%d %d", &n, &m) != EOF)

	{

		for(int i = 0; i <= n; i++)

			G[i].clear();

		while(m--)

		{

			int u, v;

			scanf("%d %d", &u, &v);

			G[u].push_back(v);

			G[v].push_back(u);

		}

		memset(color, 0, sizeof(color));

		int flag = 0;

		for(int i = 1; i <= n; i++)

			if(!color[i])

			{

				color[i] = 1;

				if(!bipartite(i))

				{

					puts("No");

					flag = 1;

					break;

				}

			}

		if(flag)

			continue;

		printf("%d\n", match());

	}

	return 0;

}