#include <iostream>
#include <memory.h>
using namespace std;
#define P 101
#define M 301
bool map[P][M];
int n,m;
int chk[M];
int match[M];
int dfs(int p)
{
int i,t;
for(i=1; i<=m; i++)
if(map[p][i] && !chk[i])
{
chk[i]=1;
t=match[i];
match[i]=p;
if(t==0 || dfs(t)) return 1;
match[i]=t;
}
return 0;
}
int mat()
{
int i, res=0;
for(i=1; i<=n; i++)
{
memset(chk, 0, sizeof(chk));
if(dfs(i)) res++;
}
return res;
}
int main()
{
int i,j,count,mi,kase;
scanf("%d",&kase);
while(kase--)
{
scanf("%d%d",&n, &m);
memset(map, 0, sizeof(map));
memset(match, 0, sizeof(match));
for(i=1; i<=n; i++)
{
scanf("%d",&count);
for(j=1; j<=count; j++)
{
scanf("%d", &mi);
map[i][mi]=1; //map[mi][i]=true;
}
}
if(mat()==n) printf("YES\n");
else printf("NO\n");
}
return 0;
}
posted on 2010-03-25 16:29
wyiu 閱讀(344)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
POJ