版权声明：本文作者靖心。靖空间地址：http://blog.csdn.net/kenden23/，未经本作者同意不得转载。 https://blog.csdn.net/kenden23/article/details/32696867

选择出一组学生。这组学生里面不能彼此之间有过恋爱史的。

又是一个典型的二分图问题。

只是须要把全部学生看成一组*2。然后求最大匹配，然后除以2. 这样事实上建图的时候。建成有向图也是能够的了。并且也是给出了两个方向的点了。

注意本题没有给出最大数是多少学生了，所以最好使用动态分配内存了。

并且本题的输入处理也特别点。要处理好，用好scanf这个函数。

#include <stdio.h>

#include <stdlib.h>

bool **stus, *used;

int *linker;

int N;

void initGraph()

{

	stus = (bool **) malloc(N * sizeof(bool *));

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

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

}

void freeGraph()

{

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

		free(stus[i]);

	free(stus);

}

bool hunDFS(int u)

{

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

	{

		if (!used[v] && stus[u][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 < N; i++)

	{

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

		if (hunDFS(i)) ans++;

		free(used);

	}

	free(linker);

	return ans>>1;

}

int main()

{

	int k, v;

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

	{

		N++;

		initGraph();

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

		{

			scanf("%d: (%d)", &v, &k);

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

			{

				scanf("%d", &v);

				stus[u][v+1] = stus[v+1][u] = true;

			}

		}

		printf("%d\n", N - 1 - hungary());

		freeGraph();

	}

	return 0;

}