pku1469.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 65 行

#include <stdio.h>
#include <string.h>
#define size 310

char p[110][size];
char v[size];
int match[size];
int P, N;

int DFS(int x)
{
	int i, t;
	for (i = 0; i < N; i++)
	{
		if (!v[i] && p[x][i] == 1)
		{
			t = match[i];
			match[i] = x;
			v[i] = 1;
			if (t == -1 || DFS(t))
				return 1;
			match[i] = t;
		}
	}
	return 0;
}

void Solve()
{
	int i, c, x, cnt;
	scanf("%d %d", &P, &N);
	memset(p, 0, sizeof(p));
	memset(match, -1, sizeof(match));
	cnt = 0;
	for (i = 0; i < P; i++)
	{
		scanf("%d", &c);
		while (c--)
		{
			scanf("%d", &x);
			p[i][x - 1] = 1;
		}
	}
	for (i = 0; i < P; i++)
	{
		memset(v, 0, sizeof(v));
		if (!DFS(i))
		{
			printf("NO\n");
			return;
		}
	}
	printf("YES\n");
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
		Solve();
	return 0;
}