分析：從第一個學生開始，先假定他任某一門課的課代表，然後再看第二個學生有沒有選的，如果第二個學生他所學的課都有人預定了，那再看預定這些課的那些學生，如果他們之間有人還可以選其他的課，則讓那個人選其他的，讓第二個人預定那個人以前定的那門課，以些類推，最後看每門課是否都有人選．這就就答案了．
[cpp]
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
struct node{
int k;
int x[305];
}f[105];
int dis[305];///dis[i]=k表示任第i門課代表的是第k個學生
bool vis[305];
int n,p;
bool DFS(int k){
for(int i=0;i<f[k].k;++i){
if(vis[f[k].x[i]])continue;
vis[f[k].x[i]]=true;
///如果第f[k].x[i]門課沒有任何人預定,或都是以前預定的那個人還可以先擇其他課
if(!dis[f[k].x[i]]||DFS(dis[f[k].x[i]])){
dis[f[k].x[i]]=k; return true;
}
}
return false;
}
int main() {
int T; cin>>T;
while(T--) {
cin>>p>>n;
bool ok=true;
for(int i=1; i<=p; ++i) {
cin>>f[i].k;
for(int j=0;j<f[i].k;++j)
cin>>f[i].x[j];
}
memset(dis,0,sizeof(dis));///初始化,所有的課都沒有課代表
for(int i=1;i<=p&&ok;++i){
memset(vis,0,sizeof(vis));///初始化,所有課都沒有"預定"課代表
ok=DFS(i);
}
if(ok)puts("YES");
else puts("NO");
}
return 0;
}
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
struct node{
int k;
int x[305];
}f[105];
int dis[305];///dis[i]=k表示任第i門課代表的是第k個學生
bool vis[305];
int n,p;
bool DFS(int k){
for(int i=0;i<f[k].k;++i){
if(vis[f[k].x[i]])continue;
vis[f[k].x[i]]=true;
///如果第f[k].x[i]門課沒有任何人預定,或都是以前預定的那個人還可以先擇其他課
if(!dis[f[k].x[i]]||DFS(dis[f[k].x[i]])){
dis[f[k].x[i]]=k; return true;
}
}
return false;
}
int main() {
int T; cin>>T;
while(T--) {
cin>>p>>n;
bool ok=true;
for(int i=1; i<=p; ++i) {
cin>>f[i].k;
for(int j=0;j<f[i].k;++j)
cin>>f[i].x[j];
}
memset(dis,0,sizeof(dis));///初始化,所有的課都沒有課代表
for(int i=1;i<=p&&ok;++i){
memset(vis,0,sizeof(vis));///初始化,所有課都沒有"預定"課代表
ok=DFS(i);
}
if(ok)puts("YES");
else puts("NO");
}
return 0;
}
