暴捜-hdu-2208-ああ、かわいい子供

タイトルリンク:
http://acm.hdu.edu.cn/showproblem.php?pid=2208
テーマ:
n人の子供がいて、お互いに好きな関係があって、AがBが好きなら、入力時にBが必ずAが好きであることを保証します.今m個の小さい風船があって、m組を超えないことができるかどうかを聞いて、各組は2人の小さい子供が互いに好きではありません.
問題解決の考え方:
伝達性がないため、デュアルコネクションには属しません.
またnは小さいので、直接捜します.
fa[i]=jは、iがjをルートとする集合であることを示す. 欲张りではなく、まず一人の子供の満足する最大の友达を全部取り除く...この考え方は間違っているので,グローバル検索をしなければならない.
コード:

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;


//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);

#define Maxn 15
int fa[Maxn];
bool edge[Maxn][Maxn];
int n,m;

bool dfs(int a,int mm) //a        ，mm           
{
   if(mm>m)
      return false;//     
   if(a==n)//           
      return true;
   for(int i=0;i<a;i++) //          
   {
      if(fa[i]!=i)
         continue;
      bool flag=true;
      for(int j=0;j<a&&flag;j++)
         if(fa[j]==i)
            flag=edge[j][a];
      if(flag)
      {
         fa[a]=i;
         if(dfs(a+1,mm))
            return true; //   
         fa[a]=a;//        
      }
   }
   if(dfs(a+1,mm+1)) //        
      return true;
   return false;
}

int main()
{
   while(~scanf("%d%d",&n,&m))
   {
      memset(edge,false,sizeof(edge));
      for(int i=0;i<n;i++)
      {
         int k,a;
         scanf("%d",&k);
         for(int j=0;j<k;j++)
            scanf("%d",&a),edge[i][a]=true;
      }
      for(int i=0;i<n;i++)
         fa[i]=i;
      if(m>=n||dfs(0,0))
         printf("YES
");
      else
         printf("NO
");
   }
   return 0;
}