[POJ]3692 Kindergarten

In a kindergarten, there are a lot of kids. All girls of the kids know each other and all boys also know each other. In addition to that, some girls and boys know each other. Now the teachers want to pick some kids to play a game, which need that all players know each other. You are to help to find maximum number of kids the teacher can pick.

这是一道求最大团的问题，我们可以转化成求补图的最大独立集。我们可以注意到，原图的补图实际上是一个二分图。因为对于男生集团和女生集团，不同种集团内部都没有边相连，只存在一段在男生集合，一段在女生集合的边。这篇文章分析过，二分图的最大独立集 = N - 最大匹配，所以我们只需要找最大匹配即可。时间复杂度O(V * E)，代码如下：

	//POJ 3692
	/*
	Description
	In a kindergarten, there are a lot of kids. All girls of the kids know each other and all boys also know each other. In addition to that, some girls and boys know each other. Now the teachers want to pick some kids to play a game, which need that all players know each other. You are to help to find maximum number of kids the teacher can pick.
	Input
	The input consists of multiple test cases. Each test case starts with a line containing three integers
	G, B (1 ≤ G, B ≤ 200) and M (0 ≤ M ≤ G × B), which is the number of girls, the number of boys and
	the number of pairs of girl and boy who know each other, respectively.
	Each of the following M lines contains two integers X and Y (1 ≤ X≤ G,1 ≤ Y ≤ B), which indicates that girl X and boy Y know each other.
	The girls are numbered from 1 to G and the boys are numbered from 1 to B.
	The last test case is followed by a line containing three zeros.
	Output
	For each test case, print a line containing the test case number( beginning with 1) followed by a integer which is the maximum number of kids the teacher can pick.
	*/
	#include <cstdio>
	#include <cstring>
	#include <algorithm>
	#include <stack>
	#include <vector>
	#include <queue>
	using namespace std;
	const int MAXN = 205;
	int graph[MAXN][MAXN], visited[MAXN], matchU[MAXN], matchV[MAXN];
	int n, m, s;//n is # of girls, m is # of boys
	bool dfs(int u)
	{
	if(visited[u])return false;
	visited[u] = 1;
	for(int v = 0; v < m; ++v)
	{
	if(graph[u][v])
	{
	if(matchV[v] == -1 || dfs(matchV[v]))
	{
	matchU[u] = v;
	matchV[v] = u;
	return true;
	}
	}
	}
	return false;
	}
	int hungarian()
	{
	int totalMatch = 0;
	memset(matchU, -1, sizeof(matchU));
	memset(matchV, -1, sizeof(matchV));
	for(int i = 0; i < n; ++i)
	{
	memset(visited, 0, sizeof(visited));
	if(matchU[i] == -1 && dfs(i))
	++totalMatch;
	}
	return totalMatch;
	}
	int main()
	{
	int x, y, t = 1;
	while(~scanf("%d%d%d", &n, &m, &s)) {
	if(n == 0 && m == 0 && s == 0)break;
	//construct complement graph
	for(int i = 0; i < n; ++i)
	for(int j = 0; j < m; ++j)
	graph[i][j] = 1;
	for(int i = 0; i < s; ++i) {
	scanf("%d%d", &x, &y);
	//we only add edge from left nodes to right nodes.
	//that is enough because we only need to dfs left part
	//since if there is augment path start in right,
	//it must end in left, and we definitely can find
	//it when search in left part. For right part, if it is
	//unmatched node, we found an augment path. If it is matched
	//node, we just want its matching information, so we don't
	//need add edge from right part to left when construct bipartite graph
	//In this case we need seperate array to record matching information
	//for left and right
	graph[x - 1][y - 1] = 0;
	}
	int maxMatch = hungarian();
	//Let G be the original graph and G' be complement graph of G.
	//G might not be bipartited, but if G‘is bipartite graph, we have:
	//maximum clique in G == maximum independent set in G' = N - maximum match in G'
	//N is total # of nodes
	printf("Case %d: %d\n",t++, n + m - maxMatch);
	}
	return 0;
	}

view raw POJ_3692_Kindergarten.cpp hosted with ❤ by GitHub