学习:请看 www.cnblogs.com/jh818012/p/3252154.html
模板题,上代码
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<cstdio> #include<cstring> #include<queue> #include<cstdlib> #include<algorithm> #include<vector> #include<cmath> using namespace std; typedef long long LL; const int N=100005; const LL mod=1e9+7; int n,m,sz; int u[N],l[N],r[N],d[N]; int col[N],row[N]; int h[1005],s[1005]; void init() { 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; sz=m; for(int i=1;i<=n;++i) h[i]=-1; } void link(int x,int y) { ++sz; ++s[y],col[sz]=y,row[sz]=x; u[sz]=u[y],d[u[y]]=sz; d[sz]=y,u[y]=sz; if(h[x]==-1)h[x]=l[sz]=r[sz]=sz; { l[sz]=l[h[x]]; r[l[h[x]]]=sz; r[sz]=h[x]; l[h[x]]=sz; } } void del(int y) { l[r[y]]=l[y]; r[l[y]]=r[y]; for(int i=d[y];i!=y;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 y) { for(int i=u[y];i!=y;i=u[i]) { for(int j=l[i];j!=i;j=l[j]) { d[u[j]]=u[d[j]]=j; ++s[col[j]]; } } r[l[y]]=l[r[y]]=y; } int ans[1005],tmp; bool dance(int pos) { if(!r[0]) { tmp=pos; return 1; } int t=r[0]; for(int i=r[0];i!=0;i=r[i]) if(s[i]<s[t])t=i; del(t); for(int i=d[t];i!=t;i=d[i]) { ans[pos]=row[i]; for(int j=r[i];j!=i;j=r[j]) del(col[j]); if(dance(pos+1))return 1; for(int j=l[i];j!=i;j=l[j]) resume(col[j]); } resume(t); return 0; } int main() { while(~scanf("%d%d",&n,&m)) { init(); for(int i=1;i<=n;++i) { int x,y; scanf("%d",&x); while(x--) { scanf("%d",&y); link(i,y); } } if(dance(0)) { printf("%d",tmp); for(int i=0;i<tmp;++i) printf(" %d",ans[i]); printf(" "); } else printf("NO "); } return 0; }