poj1469-二分图选课

题目大意：

给你p门课程和n个学生，一个学生可以选0门，1门，或者多门课程，现在要求一个由p个学生组成的集合，满足下列2个条件：

1.每个学生选择一个不同的课程

2.每个课程都有不同的代表

如果满足，就输出YES

题解：直接用二分图最大匹配即可，得到的匹配数如果等于课堂个数，则输出YES

#include<iostream>
using namespace std;
#define MAXSIZE 310
int map[MAXSIZE][MAXSIZE];
int vis[MAXSIZE];//是否拜访过
int isWho[MAXSIZE];//记录右边的点已经被左边哪个点占有
int dfs(int x ,int n)
{
	int i;
	for(i=1;i<=n;i++)//遍历右边所有点
	{
		if(!vis[i]&&map[x][i])//如果没有拜访过 并且有边存在
		{
			vis[i]=1;
			if(isWho[i]==-1||dfs(isWho[i],n))//如果这个点现在还没人要 或者可以腾出位置 注意是dfs(isWho[i])
			{
				isWho[i]=x;
				return 1;
			}
		}
	}
	return  0;
}
int main()
{
	int num,n,p,i;
	//freopen("in.txt","r",stdin);
	scanf("%d",&num);
	while(num--)
	{
		memset(map,0,sizeof(map));
		memset(isWho,-1,sizeof(isWho));
		scanf("%d%d",&p,&n);//p代表 课堂个数  n代表学生个数
		for(i=1;i<=p;i++)
		{
			int t;
			scanf("%d",&t);
			while(t--)
			{
				int t1;
				scanf("%d",&t1);
				map[i][t1]=1;
			}

		}
		int ans=0;
		for(i=1;i<=p;i++)
		{
			memset(vis,0,sizeof(vis));
			if(dfs(i,n))
				ans++;
		}
		printf("%s\n", ans == p ? "YES" : "NO");  


	}
	return 0;
}