唉，可愛的小朋友
Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 882 Accepted Submission(s): 244
Problem Description
唉，小朋友是比較麻煩的。在一個幼兒園裡，老師要上一節游戲課，有N個小朋友要玩游戲，做游戲時要用小皮球，但是幼兒園裡只有M個小皮球，而且有些小朋友不喜歡和一些小朋友在一起玩，而只喜歡和另一些小朋友一起玩，比如傻妞只喜歡和傻瓜，傻根，傻蛋們一起玩，傻根又不喜歡和傻蛋一起玩，傻蛋喜歡和傻子一起玩。所以老師只好把他們分組，每個組至少有一個小球可以玩，而且每個組內不會有兩個小朋友，相互不喜歡。現在給你這樣一個幼兒園裡小朋友之間關系的描述，做為老師，是否可以上好這節游戲課。
Input
數據有多個case，每個case先輸入兩個值N（1<=N<=10）和M(1<=M<=10)，表示有N個小朋友（從0到N-1標號），和M個小皮球。接著有N行，第i行先輸入一個K（0<=K<N），表示第i個小朋友有喜歡一起玩的其他小朋友的個數，然後後面有K個整數，表示K個小朋友的標號（不重復）。如果A喜歡和B一起玩，則B也喜歡和A一起玩，這個數據在輸入時保證。兩個case之間有空行
Output
對於每個case，如果老師可以上好課，輸出YES，否則NO。
Sample Input
3 2
2 1 2
2 2 0
2 0 1
Sample Output
YES
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<map> #include<iomanip> #define INF 99999999 using namespace std; const int MAX=10+10; bool mark[MAX][MAX]; int n,m,k,a,sum; int father[MAX]; void dfs(int id,int num){ if(num>m)return; if(sum != -1)return; if(id == n){sum=num;return;} dfs(id+1,num+1); for(int i=0;i<id;++i){ if(father[i] != i)continue;//找集合的根 int temp=1; for(int j=i;j<id && temp;++j){ if(father[j] == i)temp=mark[id][j];//判斷該點是否能進入集合i(即是否和集合中的人互相喜歡) } if(temp){father[id]=i;dfs(id+1,num);}//滿足條件該點可以進入集合 } father[id]=id; } void Init(int &n){ memset(mark,false,sizeof mark); for(int i=0;i<n;++i)father[i]=i; } int main(){ while(cin>>n>>m){ Init(n); for(int i=0;i<n;++i){ cin>>k; while(k--){ cin>>a; mark[i][a]=true; } } sum=-1; dfs(1,1);//查詢下一個人所屬集合和已有幾個集合 if(sum != -1)cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }
