学步园

题意：N行M列的0 1矩阵(1 <= N,M <= 1000)，求选出其中的一些行，使得选出的这些行每列有且仅有一个1，输出选出行的行号，无解输出"NO"。

题目链接：http://acm.hust.edu.cn/problem/show/1017

——>>DLX 练手。。

#include <cstdio>
#include <cstring>

const int MAXN = 1000 + 10;
const int MAXNODE = MAXN * MAXN;

struct DLX
{
    int sz;
    int H[MAXN], S[MAXN];
    int row[MAXNODE], col[MAXNODE];
    int U[MAXNODE], D[MAXNODE], L[MAXNODE], R[MAXNODE];
    int ret[MAXN], cnt;

    void Init(int n)
    {
        for (int i = 0; i <= n; ++i)
        {
            U[i] = D[i] = i;
            L[i] = i - 1;
            R[i] = i + 1;
        }
        L[0] = n;
        R[n] = 0;

        sz = n + 1;
        cnt = 0;
        memset(S, 0, sizeof(S));
        memset(H, -1, sizeof(H));
    }

    void Link(const int& r, const int& c)
    {
        row[sz] = r;
        col[sz] = c;
        D[sz] = D[c];
        U[D[c]] = sz;
        D[c] = sz;
        U[sz] = c;
        if (H[r] == -1)
        {
            H[r] = L[sz] = R[sz] = sz;
        }
        else
        {
            R[sz] = R[H[r]];
            L[R[H[r]]] = sz;
            R[H[r]] = sz;
            L[sz] = H[r];
        }
        S[c]++;
        sz++;
    }

    void Remove(const 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 Restore(const int& c)
    {
        for (int i = U[c]; i != c; i = U[i])
        {
            for (int j = L[i]; j != i; j = L[j])
            {
                S[col[j]]++;
                U[D[j]] = j;
                D[U[j]] = j;
            }
        }
        L[R[c]] = c;
        R[L[c]] = c;
    }

    bool Dfs(int cur)
    {
        if (R[0] == 0)
        {
            cnt = cur;
            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])
        {
            ret[cur] = row[i];
            for (int j = R[i]; j != i; j = R[j])
            {
                Remove(col[j]);
            }
            if (Dfs(cur + 1)) return true;
            for (int j = L[i]; j != i; j = L[j])
            {
                Restore(col[j]);
            }
        }
        Restore(c);

        return false;
    }

    void Solve()
    {
        if (!Dfs(0))
        {
            puts("NO");
        }
        else
        {
            printf("%d", cnt);
            for (int i = 0; i < cnt; ++i)
            {
                printf(" %d", ret[i]);
            }
            puts("");
        }
    }
} dlx;

int N, M;

void Read()
{
    int cnt, c;

    dlx.Init(M);
    for (int i = 1; i <= N; ++i)
    {
        scanf("%d", &cnt);
        while (cnt--)
        {
            scanf("%d", &c);
            dlx.Link(i, c);
        }
    }
}

int main()
{
    while (scanf("%d%d", &N, &M) != EOF)
    {
        Read();
        dlx.Solve();
    }

    return 0;
}