ダンスチェーン(DLX)テンプレート.

 
  
 
   
#define CL(a,num) memset((a),(num),sizeof(a))

#define inf 0x7f7f7f7f

#define M 1007

#define N 1000007



const int head = 0;

int u[N],d[N],l[N],r[N],c[N],row[N];

int s[M],o[M];

int ak,n,m;



void init(int m){

    int i;

    for (i = 1; i <= m; ++i){

        l[i] = i - 1;

        r[i] = i + 1;

        u[i] = d[i] = i;

        c[i] = i;

        s[i] = 0;

    }

    l[head] = m; r[head] = 1;

    r[m] = head;

}



void remove(int ci){

    int i,j;

    l[r[ci]] = l[ci];

    r[l[ci]] = r[ci];



    for (i = d[ci]; i != ci; i = d[i]){

        for (j = r[i]; j != i; j = r[j]){

            u[d[j]] = u[j];

            d[u[j]] = d[j];

            s[c[j]]--;

        }

    }

}

void resume(int ci){

    int i,j;

    l[r[ci]] = r[l[ci]] = ci;

    for (i = u[ci]; i != ci; i = u[i]){

        for (j = l[i]; j != i; j = l[j]){

            u[d[j]] = d[u[j]] = j;

            s[c[j]]++;

        }

    }

}

int dfs(int k){

    int i,j;

    //      ，         ，   

    if (r[head] == head){

        ak = k;

        return 1;

    }

    //       1   

    int MIN = inf, ci = 0;

    for (i = r[head]; i != head; i = r[i]){

        if (s[i] < MIN){

            MIN = s[i];

            ci = i;

        }

    }

    remove(ci);//               

    for (i = d[ci]; i != ci; i = d[i]){

        for (j = r[i]; j != i; j = r[j]){

            remove(c[j]);//  i    c   ，            

        }

        o[k] = row[i];//    

        if (dfs(k + 1)) return 1;//     



    //i       i 

        for (j = l[i]; j != i; j = l[j]){

            resume(c[j]);

        }

    }

    resume(ci);

    return 0;

}

int main(){

    int i,j;

    int num,size;

    while (~scanf("%d%d",&n,&m)){

      //     

       init(m);

        size = m + 1;//     

        int x;

        for (i = 0; i < n; ++i){

            scanf("%d",&num);

            int rh = -1;

            for (j = 0; j < num; ++j){

                scanf("%d",&x);



                s[x]++;//  x     1

                c[size] = x;//   size   

                row[size] = i + 1;//   size   

        //   ，  

                u[size] = u[x];

                d[u[x]] = size;

                u[x] = size;

                d[size] = x;



        //   ，  

                if (rh == -1){

                    l[size] = r[size] = size;

                    rh = size;

                }

                else{

                    l[size] = l[rh];

                    r[l[rh]] = size;

                    l[rh] = size;

                    r[size] = rh;

                }

                size++;

            }

        }

        if (dfs(0)){

            printf("%d",ak);

            for (i = 0; i < ak; ++i) printf(" %d",o[i]);

            printf("
");

        }

        else{

            printf("NO
");

        }

    }

    return 0;

}

  
 
  
　　
 
  
http://blog.csdn.net/mu399/article/details/7627736