#include <stdio.h>
#include <string.h>
#define N 1000 //最多N行N列
#define inf 10000000
int posx[N][N], posy[N][N];
typedef struct Node
{
int key;
int cnt; //此列有几个1
struct Node *root; //指向列头
struct Node *up;
struct Node *down;
struct Node *left;
struct Node *right;
}Node;
Node link[N*N]; //十字链表
int column, raw; //列数,行数
int flag, top, stack[N];
int build()
{
int i, j;
int cur, pre, first;
//构造列头, link[0]是head,link[1]---link[column]是列头, link[column]之后的是有1的节点
for(i=1; i<=column; i++)
{
link[i-1].right = &link[i];
link[i].left = &link[i-1];
link[i].cnt = 0;
link[i].key = i;
}
link[0].left = &link[column];
link[0].key = 0;
link[column].right = &link[0];
/*deal with column*/
for(i=1; i<=column; i++)
{
cur = posy[i][1] * N + i;
pre = cur;
link[cur].up = &link[i];
link[i].down = &link[cur];
link[cur].root = &link[i];
link[cur].key = cur;
link[i].cnt++;
for(j=2; j<=posy[i][0]; j++)
{
cur = posy[i][j] * N + i;
link[pre].down = &link[cur];
link[cur].key = cur;
link[cur].up = &link[pre];
link[cur].root = &link[i];
link[i].cnt++;
pre = cur;
}
link[pre].down = &link[i];
link[i].up = &link[pre];
if(link[i].cnt == 0)
return 0;
}
/*deal with rows*/
for(i=1; i<=raw; i++)
{
first = i*N+posx[i][1];
pre = first;
for(j=2; j<=posx[i][0]; j++)
{
cur = i*N+posx[i][j];
link[pre].right = &link[cur];
link[cur].left = &link[pre];
pre = cur;
}
link[pre].right = &link[first];
link[first].left = &link[pre];
}
// print();
return 1;
}
//移除列,同时把一行上的1都移除
void remove1(Node *c)
{
Node *p, *q;
c->left->right = c->right;
c->right->left = c->left;
for(p=c->down; p->key!=c->key; p=p->down)
{
p->root->cnt--;
for(q=p->right; q->key!=p->key;q=q->right)
{
q->down->up = q->up;
q->up->down = q->down;
}
}
}
//把移除的恢复
void resume(Node *c)
{
Node *p, *q;
c->right->left = c;
c->left->right = c;
for(p=c->up; p->key!=c->key; p=p->up)
{
p->root->cnt++;
for(q=p->left; q->key!=p->key; q=q->left)
{
q->up->down = q;
q->down->up=q;
}
}
}
int dfs(int k)
{
int i;
int s;
Node *c, *p, *q;
if(flag)
return 1;
if(link[0].right == &link[0])
{
printf("%d", top);
for(i=0; i<top; i++)
printf(" %d", stack[i]);
printf("\n");
flag = 1;
return 1;
}
//找到1最少的列, 这个不搞也行,只是为了优化
s = inf;
for(p=link[0].right; p->key != link[0].key; p=p->right)
{
if(p->cnt < s)
{
s = p->cnt;
c = p;
}
}
remove1(c);
/* printf("after remove %d: \n",c->key);//////////////////
print();/////////////////////////////////////////
*/
for(p=c->down; p->key!=c->key; p=p->down)
{
stack[top++] = p->key/N;
for(q=p->right; q->key!=p->key; q=q->right)
{
remove1(q->root);
}
if(dfs(k+1))
return 1;
for(q=p->left; q->key!=p->key; q=q->left)
{
resume(q->root);
}
top--;
}
resume(c);
return 0;
}
int main()
{
int i, j, tmp;
freopen("1017.in", "r", stdin);
while(scanf("%d %d", &raw, &column) != EOF)
{
memset(posx, 0, sizeof(posx));
memset(posy, 0, sizeof(posy));
memset(stack, 0, sizeof(stack));
memset(link, 0, sizeof(link));
for(i=1; i<=raw; i++)
{
scanf("%d", &posx[i][0]);
for(j=1; j<=posx[i][0]; j++)
{
scanf("%d", &tmp);
posx[i][j] = tmp;
posy[tmp][++posy[tmp][0]] = i;
}
}
if(build() == 0)
{
printf("NO\n");
continue;
}
flag = 0;
top = 0;
dfs(0);
if(!flag)
printf("NO\n");
}
return 0;
}
|