hdu 2208（dfs)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2208

思路：应用了并查集的思想，具体见注释;

#include<iostream>
const int MAXN=14;
using namespace std;
bool map[MAXN][MAXN];
int root[MAXN];
int N,M;

//n为当前的点，m为目前的气球数目
bool dfs(int n,int m){
    if(m>M)return false;
    if(n==N)return true;//搜到的最大的点为n-1;
    for(int i=0;i<n;i++){
        if(root[i]!=i)continue;//找每个集合的根
        bool flag=true;
        for(int j=i;j<n&&flag;j++){
            if(root[j]==i)flag=map[j][n];//必须保证集合里的所有的小盆友都不冲突
        }
        if(flag){
            root[n]=i;//可以加入集合，合并
            if(dfs(n+1,m))return true;
            root[n]=n;//也可以不加入
        }
    }
    if(dfs(n+1,m+1))return true;//如果都不满足要求，则搜下一个小盆友，气球数目增加
}

int main(){
    while(~scanf("%d%d",&N,&M)){
        memset(map,false,sizeof(map));
        for(int i=0;i<N;i++){
            int k,x;
            scanf("%d",&k);
            for(int j=0;j<k;j++){
                scanf("%d",&x);
                map[i][x]=true;
            }
        }
        for(int i=0;i<N;i++)root[i]=i;
        if(N<=M||dfs(0,0)){
            printf("YES\n");
        }else 
            printf("NO\n");
    }
    return 0;
}