传送门：HUST1017

【题意】给定一个由0-1组成的矩阵，是否能找到一个行的集合，使得集合中每一列都恰好包含一个1。

【分析】学习了DLX，DLX模版题，详情跳跃的舞者，舞蹈链（Dancing Links）算法——求解精确覆盖问题关于一点，恢复的时候需要倒过来可以加快速度，正着恢复会有很多已经恢复过的再重复恢复，导致没列计数不准确，速度会慢很多。所以一般倒着恢复再加每列计数。

【AC CODE】184ms

    #include <cstdio>
    #include <cstring>
    #include <cctype>
    #include <cmath>
    #include <set>
    //#include <unordered_set>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <string>
    #include <algorithm>
    using namespace std;
    typedef long long LL;
    #define rep(i,a,n) for(int i = a; i < n; i++)
    #define repe(i,a,n) for(int i = a; i <= n; i++)
    #define per(i,n,a) for(int i = n; i >= a; i--)
    #define clc(a,b) memset(a,b,sizeof(a))
    const int INF = 0x3f3f3f3f, MAXN = 1000+10, M = MAXN*100;
    int n,m;
    /*行标，列标都是1~n,和1~m*/
    struct DLX{
    private:
    	int lt[M],rt[M],up[M],down[M],row[M],col[M],tol;//舞蹈链(交叉十字循环双向链)内存池
    	int cnt[MAXN];//每一列还有多少个结点
    	void remove(int c)//删除c列含有1的全部行
    	{
    		lt[rt[c]] = lt[c];rt[lt[c]] = rt[c];
    		for(int i = down[c]; i != c; i = down[i])
    		{
    			for(int j = rt[i]; j != i; j = rt[j])
    			{
    				down[up[j]] = down[j];up[down[j]] = up[j];
    				--cnt[col[j]];
    			}
    		}
    	}
    	void reset(int c)//恢复被删除的c列含有1的全部行
    	{
    		for(int i = up[c]; i != c; i = up[i])
    		{
    			for(int j = lt[i]; j != i; j = lt[j])
    			{
    				down[up[j]] = up[down[j]] = j;
    				++cnt[col[j]];
    			}
    		}
    		lt[rt[c]] = rt[lt[c]] = c;
    	}
    public:
    	void init(int m)//总共有m列
    	{
    		repe(i,0,m)//第0行的虚拟结点
    		{
    			lt[i] = i-1,rt[i] = i+1;
    			up[i] = down[i] = i;
    		}
    		lt[0] = m;rt[m] = 0;//循环
    		tol = m+1;
    		clc(cnt,0);
    	}
    	void add_row(int r,int len, int *a)//向舞蹈链r行添加一整行结点
    	{
    		int ft = tol;
    		rep(i,0,len)
    		{
    			int c = a[i];
    			row[tol] = r,col[tol] = c;
    			lt[tol] = tol-1,rt[tol] = tol+1,up[tol] = up[c],down[tol] = c;
    			down[up[c]] = tol,up[c] = tol;
    			cnt[c]++,tol++;
    		}
    		lt[ft] = tol-1, rt[tol-1] = ft;
    	}
    	int ansd,ans[MAXN];
    	bool dance(int d)
    	{
    		if(0 == rt[0])//所有列都被覆盖,找到答案
    		{
    			ansd = d;
    			return true;
    		}
    		int c = rt[0];//第一个没被覆盖的列c
    		for(int i = rt[0]; i; i= rt[i]) if(cnt[i] < cnt[c]) c = i;//优化，选择列上行数最小的那列，可以减少重复覆盖的概率，加快搜索
    		remove(c);
    		for(int i = down[c];i != c; i = down[i])//删除c列为1的所有行
    		{
    			ans[d] = row[i];
    			for(int j = rt[i]; j != i; j = rt[j]) remove(col[j]);//把删除行所占的列也删除
    			if(dance(d+1)) return true;
    			for(int j = lt[i]; j != i; j = lt[j]) reset(col[j]);
    		}
    		reset(c);
    		return false;
    	}
    }dlx;

    int main()
    {
    #ifdef SHY
    	freopen("d:\\1.txt", "r", stdin);
    #endif
    	while(~scanf("%d %d", &n, &m))
    	{
    		int a[110];
    		dlx.init(m);
    		repe(i,1,n)
    		{
    			int len;
    			scanf("%d", &len);
    			rep(j,0,len) scanf("%d",&a[j]);
    			sort(a,a+len);
    			dlx.add_row(i,len,a);
    		}
    		if(dlx.dance(0))
    		{
    			printf("%d",dlx.ansd);
    			rep(i,0,dlx.ansd) printf(" %d", dlx.ans[i]);
    			putchar('\n');
    		}
    		else puts("NO");
    	}
    	return 0;
    }