一个男女搭配的关系图，看能够凑成多少对，基本和最原始的一个二分图谜题一样了，就是 一个岛上能够凑成多少对夫妻的问题。

所以是典型的二分图问题。

使用匈牙利算法，写成两个函数，就很清晰了。

本程序还带分配释放程序，当然oj一般不须要。可是好的程序一定要。

#include <stdio.h>

#include <stdlib.h>

int K, M, N, a, b;

int *linker;

bool **gra, *used;

void initGraph()

{

	gra = (bool **) malloc(M * sizeof(bool*));//注意是bool*不是bool

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

		gra[i] = (bool *) calloc(N, sizeof(bool));

}

void freeGraph()

{

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

		free(gra[i]);

	free(gra);

}

bool hunDFS(int u)

{

	for (int v = 1; v < N; v++)

	{

		if (gra[u][v] && !used[v])

		{

			used[v] = true;

			if (!linker[v] || hunDFS(linker[v]))

			{

				linker[v] = u;

				return true;

			}

		}

	}

	return false;

}

int hungary()

{

	int ans = 0;

	linker = (int *) calloc(N, sizeof(int));

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

	{

		used = (bool *) calloc(N, sizeof(bool));

		if (hunDFS(i)) ans++;

		free(used);

	}

	free(linker);

	return ans;

}

int main()

{

	while (scanf("%d %d %d", &K, &M, &N) != EOF && K)

	{

		M++, N++;//下标从1開始，0不使用

		initGraph();

		while (K--)

		{

			scanf("%d %d", &a, &b);

			gra[a][b] = true;

		}

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

		freeGraph();

	}

	return 0;

}