2288846_ac_250ms_76k.c

来自「北大大牛代码 1240道题的原代码 超级权威」· C语言 代码 · 共 65 行

#include <stdio.h>
#include <string.h>

int n, p;
int map[301][101];
int link[301], b[301];
int dfs(int v)
{
	int i;

	for(i = 1; i <= map[v][0]; i++)
	{
		if(!b[map[v][i]])
		{
			b[map[v][i]] = 1;
			if(!link[map[v][i]]||dfs(link[map[v][i]]))
			{
				link[map[v][i]] = v;
				return 1;
			}
		}
	}
	return 0;
}

void input()
{
	int i, j;
	int ans;

	scanf("%d%d",&p,&n);
	memset(link,0,sizeof(link));
	for(i = 1; i <= p; i++)
	{
		scanf("%d",&map[i][0]);
		for(j = 1; j <= map[i][0]; j++)
			scanf("%d",&map[i][j]);
	}
	if(n<p)
	{
		printf("NO\n");
		return ;
	}
	ans = 0;
	for(i = 1; i <= p; i++)
	{
		memset(b,0,sizeof(b));
		if(!dfs(i))
		{
			printf("NO\n");
			return ;
		}
	}
	printf("YES\n");
}

int main()
{
	int t;

	scanf("%d",&t);
	while(t--)
		input();
	return 1;
}