Exact cover HUST

There is an N*M matrix with only 0s and 1s, (1 <= N,M <= 1000). An exact cover is a selection of rows such that every column has a 1 in exactly one of the selected rows. 
Try to find out the selected rows. 
InputThere are multiply test cases. 
First line: two integers N, M; 
The following N lines: Every line first comes an integer C(1 <= C <= 100), represents the number of 1s in this row, then comes C integers: the index of the columns whose value is 1 in this row. 
OutputFirst output the number of rows in the selection, then output the index of the selected rows. 
If there are multiply selections, you should just output any of them. 
If there are no selection, just output "NO". 
Sample Input

6 7
3 1 4 7
2 1 4
3 4 5 7
3 3 5 6
4 2 3 6 7
2 2 7

Sample Output

3 2 4 6

题意，从一个n*m的矩阵选若干行，使得每列在所选行中恰好有一个1。输入 第一行：两个整数N，M; 
以下N行：每行首先出现一个整数C（1 <= C <= 100），表示该行中1的个数，然后是C个整数：该行中值为1的列的索引。 
输出：首先输出选择中的行数，然后输出所选行的索引。 
如果有多个选择，您应该只输出它们中的任何一个。 
如果没有选择，只输出“NO”。 

思路：精确覆盖问题用Dancing Links X 算法求解，详细情况见代码

代码：

#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <iostream>
#define mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;

struct{
    int n,m;//n表示行数，m表是列数
    int left[1001010],right[1001010],up[1001010],down[1001010],col[1001010],row[1001010];
    //  左，右，上，下，列，行
    int head[1010],ans[1010];
    //   头，答案
    int ansed,size;
    //   计数，标识
    void init(int _n,int _m)//初始化数据
    {
        n=_n;
        m=_m;
        //建立矩阵的第0行
        for(int i=0;i<=m;i++)
        {
            up[i]=i;
            down[i]=i;
            left[i]=i-1;
            right[i]=i+1;
            col[i]=i;
            row[i]=0;
        }
        left[0]=m;
        right[m]=0;
        size=m;
        memset(head,-1,sizeof(head));
        memset(ans,0,sizeof(ans));
        ansed=0;
        return ;
    }
    //插入数据
    void insert(int r,int c)
    {
        size++;//矩阵中存入的数是size
        down[size]=down[c];
        up[size]=c;
        up[down[c]]=size;
        down[c]=size;
        row[size]=r;
        col[size]=c;
        if(head[r]<0)//每一行存入第一个数时
        {
            head[r]=size;
            left[size]=right[size]=size;
        }
        else
        {
            left[size]=head[r];
            right[size]=right[head[r]];
            left[right[head[r]]]=size;
            right[head[r]]=size;
        }
        return ;
    }
    //删除数据的一列和每列对应的行
    void delet(int c)
    {
        //删除一列
        right[left[c]]=right[c];
        left[right[c]]=left[c];
        //删除行
        for(int i=down[c];i!=c;i=down[i])//往下循环此列的每一个数
        {
            for(int j=right[i];j!=i;j=right[j])//i所在行往右循环每一个数
            {
                down[up[j]]=down[j];
                up[down[j]]=up[j];
            }
        }
        return ;
    }
    //恢复数据的一列和每列对应的行
    void reback(int c)
    {
        //恢复行
        for(int i=up[c];i!=c;i=up[i])//往上循环此列的每一个数
        {
            for(int j=left[i];j!=i;j=left[j])//i所在行往左循环每一个数
            {
                down[up[j]]=j;
                up[down[j]]=j;
            }
        }
        //恢复一列
        right[left[c]]=c;
        left[right[c]]=c;
        return ;
    }
    //主循环
    bool dancing(int dep)
    {
        if(right[0]==0)//如果Head.Right=Head，退出
        {
            ansed=dep;
            return true;
        }
        int c=right[0];
        delet(c);//删除上述步骤2的紫色方块
        for(int i=down[c];i!=c;i=down[i])
        {
            ans[dep]=row[i];
            //删除上述步骤3中的橙色方块
            for(int j=right[i];j!=i;j=right[j])
            {
                delet(col[j]);
            }
            //模拟删除后的矩阵
            if(dancing(dep+1))
            {
                return true;
            }
            //恢复被删除的数据
            for(int j=left[i];j!=i;j=left[j])
            {
                reback(col[j]);
            }
        }
        return false;
    }
}dlx;
int main()
{
    int n,m,p,k;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        dlx.init(n,m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&p);
            for(int j=1;j<=p;j++)
            {
                scanf("%d",&k);
                //插入第i行第k列的数
                dlx.insert(i,k);
            }
        }
        //判断是否有结果
        if(!dlx.dancing(0))
        {
            printf("NO
");
        }
        else
        {
            printf("%d",dlx.ansed);
            for(int i=0;i<dlx.ansed;i++)
            {
                printf(" %d",dlx.ans[i]);
            }
            printf("
");
        }
    }
    return 0;
}