题目链接：点这里！！！
题解：Dancing Links第一题，抄了几下kuangbin的板子，感觉这东西真TM的吊！！
推荐篇blog:http://www.cnblogs.com/grenet/p/3145800.html
代码：
#include<cstdio> #include<cstring> #include<iostream> #include<sstream> #include<algorithm> #include<vector> #include<bitset> #include<set> #include<queue> #include<stack> #include<map> #include<cstdlib> #include<cmath> #define pb push_back #define pa pair<int,int> #define clr(a,b) memset(a,b,sizeof(a)) #define lson lr<<1,l,mid #define rson lr<<1|1,mid+1,r #define bug(x) printf("%d++++++++++++++++++++%d\n",x,x) #define key_value ch[ch[root][1]][0] #pragma comment(linker, "/STACK:102400000000,102400000000") typedef long long LL; const LL MOD = 1000000007; const int N = 55; const int maxn = 1e6+15; const int letter = 130; const int INF = 1e9; const double pi=acos(-1.0); const double eps=1e-10; using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; const int maxnode = 1e5+15; const int maxh=1000+15; struct dlx{ int n,m,size; int U[maxnode],D[maxnode],L[maxnode],R[maxnode]; int row[maxnode],col[maxnode]; int H[maxh],S[maxh]; int ansd,ans[maxh]; void init(int _n,int _m){ n=_n,m=_m; for(int i=0;i<=m;i++){ S[i]=0; U[i]=D[i]=i; L[i]=i-1; R[i]=i+1; } R[m]=0,L[0]=m; size=m; for(int i=1;i<=n;i++) H[i]=-1; } void link(int r,int c){ ++S[col[++size]=c]; row[size]=r; D[size]=D[c]; U[D[c]]=size; U[size]=c; D[c]=size; if(H[r]<0) H[r]=L[size]=R[size]=size; else { R[size]=R[H[r]]; L[R[H[r]]]=size; L[size]=H[r]; R[H[r]]=size; } } void remove(int c){ L[R[c]]=L[c],R[L[c]]=R[c]; for(int i=D[c];i!=c;i=D[i]) for(int j=R[i];j!=i;j=R[j]){ U[D[j]]=U[j]; D[U[j]]=D[j]; --S[col[j]]; } } void resume(int c){ for(int i=U[c];i!=c;i=U[i]) for(int j=L[i];j!=i;j=L[j]) ++S[col[U[D[j]]=D[U[j]]=j]]; L[R[c]]=R[L[c]]=c; } bool dance(int d){ if(R[0]==0){ansd=d;return true;} int c=R[0]; for(int i=R[0];i!=0;i=R[i]) if(S[i]<S[c]) c=i; remove(c); for(int i=D[c];i!=c;i=D[i]){ ans[d]=row[i]; for(int j=R[i];j!=i;j=R[j]) remove(col[j]); if(dance(d+1)) return true; for(int j=L[i];j!=i;j=L[j]) resume(col[j]); } resume(c); return false; } }cc; int main(){ while(~scanf("%d%d",&n,&m)){ cc.init(n,m); for(int i=1;i<=n;i++){ int p,j; scanf("%d",&p); while(p--){ scanf("%d",&j); cc.link(i,j); } } if(!cc.dance(0)) puts("NO"); else { printf("%d",cc.ansd); for(int i=0;i<cc.ansd;i++) printf(" %d",cc.ans[i]); puts(""); } } return 0; } /* 5 5 2 1 5 3 3 4 5 1 2 2 3 4 3 1 2 5 5 5 0 0 0 0 2 2 3 */