template <int MXNODE = 5000> // 稀疏矩阵最大点数
struct DLX {
    int n, m, cur; // 行 列 新节点指针
    int h[MXNODE];  //每行的头指针
    int u[MXNODE], d[MXNODE], l[MXNODE], r[MXNODE]; //每个点的上下左右指针
    int row[MXNODE], col[MXNODE]; //每个点所在行,列
    int s[MXNODE]; //每列的节点数
    int ans[MXNODE]; //选了那些行

    DLX(int n, int m): n(n), m(m) {
        cur = 0;
        memset(h, 0, sizeof(u));
        memset(u, 0, sizeof(u));
        memset(d, 0, sizeof(d));
        memset(l, 0, sizeof(l));
        memset(r, 0, sizeof(r));
        memset(row, 0, sizeof(row));
        memset(col, 0, sizeof(col));
        memset(s, 0, sizeof(s));
        memset(ans, 0, sizeof(ans));
        init();
    }

    void init(){ //初始化第0行的列表头
        for(int y=0; y<=m; y++){
            u[y] = d[y] = y;
            l[y] = y-1; r[y] = y+1;
        }
        l[0]=m; r[m]=0; cur=m+1; //下一个点的编号
    }
    //尾插法 要逐行逐列顺序插入
    void link(int x,int y){ //在x行y列插入点 
        row[cur]=x; col[cur]=y; s[y]++;
        // 列表头y，原先y <--> u[y]，变为y <--> cur <--> u[y]
        u[cur]=u[y]; // cur --> u[y]
        d[u[y]]=cur; // cur <--> u[y]
        d[cur]=y; // y <-- cur <--> u[y]
        u[y]=cur; // y <--> cur <--> u[y]

        // 行表头h[x]
        if (h[x] == 0) {
            h[x] = r[cur] = l[cur] = cur;
        } else {
            // 原先 l[h[x]] <--> h[x]，变为l[h[x]] <--> cur <--> h[x]
            l[cur]=l[h[x]]; // l[h[x]] <-- cur
            r[l[h[x]]]=cur; // l[h[x]] <--> cur
            r[cur]=h[x]; // l[h[x]] <--> cur --> h[x]
            l[h[x]]=cur; // l[h[x]] <--> cur <--> h[x]
        }
        cur++;
    }
    void remove(int y){ //删除y列与关联行
        /*
            a <--> b <--> c
            to
            a <-- b --> c
              <------->
        */
        r[l[y]]=r[y], l[r[y]]=l[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){ //恢复y列与关联行
        r[l[y]]=y, l[r[y]]=y;  
        for(int i=u[y]; i!=y; i=u[i])   //向上
            for(int j=l[i]; j!=i; j=l[j]) //向左
                u[d[j]]=j, d[u[j]]=j, s[col[j]]++;
    }
    bool dance(int dep){
        if(r[0]==0){
            for (int i=0; i<dep; i++) {
                cout << ans[i] << " ";
            }
            cout << "\\n";
            return true;
        }

        int y=r[0]; //找到点最少的列
        for(int i=r[0];i;i=r[i]) if(s[i]<s[y]) y=i;
        remove(y);
        for(int i=d[y];i!=y;i=d[i]) {
            //在y列含1的行中选择一行作为答案，这一行存在1的列也需要关联删除才能保证精准覆盖
            ans[dep]=row[i]; 
            for(int j=r[i];j!=i;j=r[j]) remove(col[j]);
            if(dance(dep+1)) return true;
            for(int j=l[i];j!=i;j=l[j]) resume(col[j]);
        }
        resume(y); 
        return false;
    }
};
/*

use:
DLX dlx(n, m);

dlx.link(i,j);

dlx.dance(0);

*/

• 37. 解数独
• 52. N 皇后 II