唉，可爱的小朋友
Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 819 Accepted Submission(s): 220
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
2 1 2
2 2 0
2 0 1
Sample Output
YES
Author
wangye
Recommend
wangye
这道题，原来不是像网上某些题解说的那样是强连通。（例如当1和2可以玩，不可以和3玩。但2可以和3玩，这样情况如果是用强连通，那样这3个人都是在一个棵里面。）神牛说是K SAT算法（属于NP算法）。所以用暴力是比较好的。题目数据那么小。
思路：让每一个人都分别属于一个不同的集合。然后判断一个点可不可以放入一个集合里，这时候要找到那个集合的根，同时，要确保这个点不与集合里面的所有点有冲突。同时，一个点可能可以放入多个集合中，那样通过一个深搜，那样就可以枚举出所有的可能，再通过一个判断，就可以知道是否有满足题意的点。
#include<iostream>
#include<cstdio>
#include<cstring> using namespace std; int n,m,map[][];
int root[],flag; void DFS(int x,int y){ //x代表人数 y代表球数
if(flag) //找到满足题意的方案
return ;
if(y>m) //需要的球超出了预算
return ;
if(x==n){ //人数达到了要求,且这时候球的数量一定在预算内,找到了可行方案
flag=;
return ;
}
for(int i=;i<x;i++){
if(root[i]!=i) //找一个集合的根
continue;
int tag=;
for(int j=i;j<x && tag;j++) //判断该点是否可以放入到该集合内
if(root[j]==i)
tag=map[j][x];
if(tag){ //tag为1的时候，则说明这个点可以放到该集合内
root[x]=i; //将这个点指向根i
DFS(x+,y); //人数加1,进入下一个递归
root[x]=x; //将该点还原,以找到下一个该点的可能落脚点,以确保可以考虑到所有的可能
}
}
DFS(x+,y+); //将这个点分到一个新的集合里
} int main(){ //freopen("input.txt","r",stdin); while(~scanf("%d%d",&n,&m)){
memset(map,,sizeof(map));
flag=;
int k,x;
for(int i=;i<n;i++){
scanf("%d",&k);
root[i]=i;
while(k--){
scanf("%d",&x);
map[i][x]=; //对无冲突的点的组合标记为真
}
}
DFS(,);
if(m>=n || flag)
puts("YES");
else
puts("NO");
}
return ;
}