题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2208
思路:应用了并查集的思想,具体见注释;
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<iostream> 2 const int MAXN=14; 3 using namespace std; 4 bool map[MAXN][MAXN]; 5 int root[MAXN]; 6 int N,M; 7 8 //n为当前的点,m为目前的气球数目 9 bool dfs(int n,int m){ 10 if(m>M)return false; 11 if(n==N)return true;//搜到的最大的点为n-1; 12 for(int i=0;i<n;i++){ 13 if(root[i]!=i)continue;//找每个集合的根 14 bool flag=true; 15 for(int j=i;j<n&&flag;j++){ 16 if(root[j]==i)flag=map[j][n];//必须保证集合里的所有的小盆友都不冲突 17 } 18 if(flag){ 19 root[n]=i;//可以加入集合,合并 20 if(dfs(n+1,m))return true; 21 root[n]=n;//也可以不加入 22 } 23 } 24 if(dfs(n+1,m+1))return true;//如果都不满足要求,则搜下一个小盆友,气球数目增加 25 } 26 27 int main(){ 28 while(~scanf("%d%d",&N,&M)){ 29 memset(map,false,sizeof(map)); 30 for(int i=0;i<N;i++){ 31 int k,x; 32 scanf("%d",&k); 33 for(int j=0;j<k;j++){ 34 scanf("%d",&x); 35 map[i][x]=true; 36 } 37 } 38 for(int i=0;i<N;i++)root[i]=i; 39 if(N<=M||dfs(0,0)){ 40 printf("YES\n"); 41 }else 42 printf("NO\n"); 43 } 44 return 0; 45 }