2288815_ac_875ms_144k.c

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

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

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

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

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

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

int main()
{
	int t;

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