舞蹈鍊 Dancing Link(DLX)

寫數獨的時候，我發現除了DFS遞迴剪枝還有另一中更快的酷做法，但當時沉浸在AC的喜悅中就沒有學，後來在洛谷河道剛好逛到這東東，才學會這酷酷演算法(但我太笨畫很久才學會)

*本篇文章大量參考這裡，因為是我學的地方，非常感謝作者大佬

• 舞蹈鍊是幹嘛的
  舞蹈鍊最主要解決的問題是精確覆蓋問題，在各個子集合中選擇若干個使其包含整個全集，並且各個子集合不重疊，上維基百科,畫個圖就是這樣
  
  
  要選擇其中幾行，使每一列都有一個
  $1$，並且選擇的行中，有
  $1$的列不能重疊
  模板題

X algorithm 舞蹈鍊的靈魂

這個問題解決的方法呢，就是暴力遞迴枚舉，具體過程如下:

1. 如果只剩一個集合(行)，並且所有元素都是
   $1$ ，代表找到解了，否則去
   $4.$
2. 選擇一個集合(行)，把其中
   $1$覆蓋到的列刪除，包括重疊到的集合(行)
3. 如果此時剩下一個集合(行)，回到
   $1.$ ，否則回到
   $2.$
4. 如果只剩一個集合(行)，且其中有元素是
   $0$ 代表先前選擇的集合有錯誤，回溯後繼續
   $2.$
   畫個圖流程大概是這樣:

• 先選擇集合(1.)，把重疊到的 (藍色) 和其 (黃色) 所在集合 (紫色) 都刪掉
  
• 把有顏色的拿掉變成這樣，只剩(3.)集合，但裡面有
  $0$，回溯到上一步
  
• 選擇集合(2.)，一樣把重複到的刪掉
  
• 剩下集合(3.)且沒有
  $0$，找到解是 : 集合(2.)和(3.)
  
  
  雖然我圖畫得很亂可能不太好懂qwq，但看懂後可以發現，演算法最大的問題在於，要怎麼實現刪除行，回溯後還要恢復，顯然這用二維陣列來處理不只難寫而且時空複雜度也會極高。
  那有什麼資料結構可以支持快速刪除和恢復呢? linked-list !

Dacing Link 舞蹈鍊

先來複習一下linked-list要怎麼刪除和恢復

假設我想刪除

$2.$節點，只要改變一下

$1.$和

$3.$的指標就好，相當於

$2.$節點消失了

不過仔細看看

$2.$節點，雖然他已經不在linked-list上了，但他的節點本身還是存在，且指標也還指向linked-list，所以我們可以透過這個特性恢復

回到Dacing Link本身，他是一個十字鍊，長這樣

其實他是一個循環鍊，也就是頭尾會相連，但太麻煩了我懶的畫。因為這些特性，他有一個非常強大的名字，十字交叉雙向循環鍊表，好但沒人會這樣叫他，我也叫他舞蹈鍊。

那怎麼建圖(鍊?)呢? 把上面的

$01$矩陣中的

$1$變成一個節點，

$0$則讓他空著，像這樣

好亂，而且怎麼跑出一堆奇怪的節點了?

• head節點 : 用途是方便我們確認答案，只是一個輔助節點
• 列節點 : 也是用判斷答案的輔助節點
• 行編號 : 集合的編號，只是畫出來比較好理解，不是一個真實的節點

有了這個資料結構，再把上面X algorithm的執行過程搬過來，你就會DLX了!

1. 如果沒有任何集合(行)存在，判斷還有沒有列節點(head.r==head)，沒有就是找到答案了
2. 如果還有集合(行)，選擇其中一個，把覆蓋到的、重複的等等節點刪除
3. 如果刪完沒有集合了，回到
   $1.$ ，否則回到
   $2.$
4. 如果沒有任何集合存在，且還有列節點存在(head.r!=head)，代表之前的決策有錯誤或根本無解，回溯並繼續遞迴枚舉

選擇(1.)集合，把覆蓋到的和其所在的集合刪除

所有集合都消失了，但還有列節點，要回溯繼續求解

選擇集合(2.)，一樣刪除該刪除的節點，(這裡

$1.$列節點應該是藍色，我畫錯了qwq)

還有集合，繼續選擇(3.)集合

沒有集合了，且列節點全空，找到答案了

忍受一下我畫的醜圖，消化一下，再來直接上程式

DLX實作

題目以上面的模板題做舉例

• 先看變數

struct nd{
    int up,dw,l,r;
    int row,col;
};
nd dl[200500];
int ans[200500],row[200500],sz[200500];
int n,m,cnt=0;

nd是存節點的結構體，dl是節點的陣列，ans紀錄最後答案，row紀錄每一行(集合)的第一個節點，sz是每一列下面有多少個節點(可以不用，用於優化)，n跟m是題目的定義，cnt用於加點

• 初始化

void init(){
    for(int i=0;i<=m;i++){
        dl[i].l=i-1;
        dl[i].r=i+1;
        dl[i].up=i;
        dl[i].dw=i;
        sz[i]=0;
    }
    dl[0].l=m;
    dl[m].r=0;
    cnt=m;
}

先處理好所有列節點，上下因為都沒有節點，所以指向自己，左右與相鄰的列節點形成環，其中dl[0]是head節點，至於row也就是行可以先不處理，因為他不是真實的點。
處理完圖會長這樣子

• 增加節點

void addnd(int r,int c){
    dl[++cnt].up=dl[c].up;
    dl[cnt].dw=c;
    dl[c].up=cnt;
    dl[dl[cnt].up].dw=cnt;
    dl[cnt].col=c;
    dl[cnt].row=r;
    sz[c]++;
    if(!row[r]){
        dl[cnt].r=cnt;
        dl[cnt].l=cnt;
        row[r]=cnt;
    }else{
        dl[cnt].r=row[r];
        dl[cnt].l=dl[row[r]].l;
        dl[row[r]].l=cnt;
        dl[dl[cnt].l].r=cnt;
    }
}

r和c是在第幾行第幾列增加節點，先把上下連好，上個圖應該比較清楚

再來就處理左右的指標，要判斷他是不是這行的第一個節點，方便更新row陣列，應該不難理解，這裡就不上圖了因為我懶，如果真的不行可以自己畫畫看

• 刪除一列

void rm(int c){
    dl[dl[c].l].r=dl[c].r;
    dl[dl[c].r].l=dl[c].l;
    for(int i=dl[c].dw;i!=c;i=dl[i].dw){
        for(int j=dl[i].r;j!=i;j=dl[j].r){
            dl[dl[j].up].dw=dl[j].dw;
            dl[dl[j].dw].up=dl[j].up;
            sz[dl[j].col]--;
        }
    }
}

最前面把這列的列節點從列的linked-list裡刪除，等同於刪除了這一列，但我們還要去枚舉刪除同在這一列的集合(行)，因為不能重複覆蓋，只刪除上下指標，代表從候選集合中刪除，但還是保留左右指標，確保同一集合連在一起，以便後續回溯復原

畫的有點超亂，希望看得懂

• 復原一列

void rc(int c){
    for(int i=dl[c].dw;i!=c;i=dl[i].dw){
        for(int j=dl[i].r;j!=i;j=dl[j].r){
            dl[dl[j].up].dw=j;
            dl[dl[j].dw].up=j;
            sz[dl[j].col]++;
        }
    }
    dl[dl[c].l].r=c;
    dl[dl[c].r].l=c;
}

就完全是刪除的反動作，枚舉所有因為這一列被刪除的集合，上下關係連回來，最後復原這一列的列節點，具體原理上面linked-list的復原有講到(雖然帶過而已)，思考一下會發現刪除跟復原的順序很巧妙。

• 最後是Dacing Link的靈魂 跳舞(X algorithm)

int dancing(int deep){
    if(dl[0].r==0){
        for(int i=1;i<deep;i++) cout<<ans[i]<<' ';
        return 1;
    }
    int C=dl[0].r;
    for(int i=dl[0].r;i!=0;i=dl[i].r){
        if(sz[i]<sz[C]) C=i;
    }
    rm(C);
    for(int i=dl[C].dw;i!=C;i=dl[i].dw){
        ans[deep]=dl[i].row;
        for(int j=dl[i].r;j!=i;j=dl[j].r) rm(dl[j].col);
        if(dancing(deep+1)==1) return 1;
        for(int j=dl[i].r;j!=i;j=dl[j].r) rc(dl[j].col);
    }
    rc(C);
    return 0;
}

先判斷是不是找到解了(head.r==head)，是的話輸出答案，不然繼續遞迴。選擇其中一列(sz的優化就在這，在洛谷會TLE，吸沒吸氧都一樣)這裡選擇節點最少的列，然後刪除，再去枚舉要選擇這一列的哪個集合，集合中所有節點所在的列刪除後遞迴下去，回溯時復原，回傳1代表找到解了，0代表還沒。

那重要的部分都講完了，整段程式在這，main()應該都看得懂，就不多說了

• AC code (155ms 4.45MB)

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct nd{
    int up,dw,l,r;
    int row,col;
};
nd dl[200500];
int ans[200500],row[200500],sz[200500];
int n,m,cnt=0;
void init(){
    for(int i=0;i<=m;i++){
        dl[i].l=i-1;
        dl[i].r=i+1;
        dl[i].up=i;
        dl[i].dw=i;
        sz[i]=0;
    }
    dl[0].l=m;
    dl[m].r=0;
    cnt=m;
}
void rm(int c){
    dl[dl[c].l].r=dl[c].r;
    dl[dl[c].r].l=dl[c].l;
    for(int i=dl[c].dw;i!=c;i=dl[i].dw){
        for(int j=dl[i].r;j!=i;j=dl[j].r){
            dl[dl[j].up].dw=dl[j].dw;
            dl[dl[j].dw].up=dl[j].up;
            sz[dl[j].col]--;
        }
    }
}
void rc(int c){
    for(int i=dl[c].dw;i!=c;i=dl[i].dw){
        for(int j=dl[i].r;j!=i;j=dl[j].r){
            dl[dl[j].up].dw=j;
            dl[dl[j].dw].up=j;
            sz[dl[j].col]++;
        }
    }
    dl[dl[c].l].r=c;
    dl[dl[c].r].l=c;
}
void addnd(int r,int c){
    dl[++cnt].up=dl[c].up;
    dl[cnt].dw=c;
    dl[c].up=cnt;
    dl[dl[cnt].up].dw=cnt;
    dl[cnt].col=c;
    dl[cnt].row=r;
    sz[c]++;
    if(!row[r]){
        dl[cnt].r=cnt;
        dl[cnt].l=cnt;
        row[r]=cnt;
    }else{
        dl[cnt].r=row[r];
        dl[cnt].l=dl[row[r]].l;
        dl[row[r]].l=cnt;
        dl[dl[cnt].l].r=cnt;
    }
}
int dancing(int deep){
    if(dl[0].r==0){
        for(int i=1;i<deep;i++) cout<<ans[i]<<' ';
        return 1;
    }
    int C=dl[0].r;
    for(int i=dl[0].r;i!=0;i=dl[i].r){
        if(sz[i]<sz[C]) C=i;
    }
    rm(C);
    for(int i=dl[C].dw;i!=C;i=dl[i].dw){
        ans[deep]=dl[i].row;
        for(int j=dl[i].r;j!=i;j=dl[j].r) rm(dl[j].col);
        if(dancing(deep+1)==1) return 1;
        for(int j=dl[i].r;j!=i;j=dl[j].r) rc(dl[j].col);
    }
    rc(C);
    return 0;
}
signed main(){
    cin>>n>>m;
    init();
    int t;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>t;
            if(t==1) addnd(i,j);
        }
    }
    if(!dancing(1)){
        cout<<"No Solution!";
    }
    cout<<'\n';
    return 0;
}

雜

看完後你可能會好奇時間複雜度? 我可以很不負責任的告訴你，我不知道，我有去找過，但每個地方說的都不一樣，我也不是證明大師，就不亂下定義了，畢竟他是遞迴枚舉，複雜度不好估算，只能等你各位大佬證明了。
至於DLX可以在甚麼場景應用? 我目前聽過數獨，八皇后等等遞迴枚舉的地方，其實只要想辦法把問題轉成精確覆蓋問題就能使用DLX，這點也是DLX最難的地方(畢竟他算是模板)，更多應用也得你各位大佬證明。

我只是個甚麼都不會的競程蒟蒻，如果這篇沒辦法讓你看懂我很抱歉qwq，那推我學的地方，如果這篇文章有任何問題，歡迎來我的DC提出(沒有問題也可以來找我聊天)