#include<stdio.h>
#include<string.h>
main()
{
bool map[100][300];
int i,i1,i2,num,num1,que[300],cou,stu,match1[100],match2[300],pque,p1,now,prev[300],n;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d%d",&cou,&stu);
memset(map,0,sizeof(map));
for(i1=0;i1<cou;i1++)
{
scanf("%d",&num);
for(i2=0;i2<num;i2++)
{
scanf("%d",&num1);
map[i1][num1-1]=true;
}
}
num=0;
memset(match1,int(-1),sizeof(match1));
memset(match2,int(-1),sizeof(match2));
for(i1=0;i1<cou;i1++)
{
p1=0;
pque=0;
for(i2=0;i2<stu;i2++)
{
if(map[i1][i2])
{
prev[i2]=-1;
que[pque++]=i2;
}
else
prev[i2]=-2;
}
while(p1<pque)
{
now=que[p1];
if(match2[now]==-1)
break;
p1++;
for(i2=0;i2<stu;i2++)
{
if(prev[i2]==-2&&map[match2[now]][i2])
{
prev[i2]=now;
que[pque++]=i2;
}
}
}
if(p1==pque)
continue;
while(prev[now]>=0)
{
match1[match2[prev[now]]]=now;
match2[now]=match2[prev[now]];
now=prev[now];
}
match2[now]=i1;
match1[i1]=now;
num++;
}
if(num==cou)
printf("YES\n");
else
printf("NO\n");
}
}
dfs实现过程：
#include<stdio.h>
#include<string.h>
#define MAX 100
bool map[MAX][MAX],searched[MAX];
int prev[MAX],m,n;
bool dfs(int data)
{
int i,temp;
for(i=0;i<m;i++)
{
if(map[data][i]&&!searched[i])
{
searched[i]=true;
temp=prev[i];
prev[i]=data;
if(temp==-1||dfs(temp))
return true;
prev[i]=temp;
}
}
return false;
}
main()
{
int num,i,k,temp1,temp2,job;
while(scanf("%d",&n)!=EOF&&n!=0)
{
scanf("%d%d",&m,&k);
memset(map,0,sizeof(map));
memset(prev,int(-1),sizeof(prev));
memset(searched,0,sizeof(searched));
for(i=0;i<k;i++)
{
scanf("%d%d%d",&job,&temp1,&temp2);
if(temp1!=0&&temp2!=0)
map[temp1][temp2]=true;
}
num=0;
for(i=0;i<n;i++)
{
memset(searched,0,sizeof(searched));
dfs(i);
}
for(i=0;i<m;i++)
{
if(prev[i]!=-1)
num++;
}
printf("%d\n",num);
}
}
