# 舞蹈鍊 Dancing Link(DLX)
寫數獨的時候，我發現除了DFS遞迴剪枝還有另一中更快的酷做法，~~但當時沉浸在AC的喜悅中就沒有學~~，後來在洛谷河道剛好逛到這東東，才學會這酷酷演算法(但我太笨畫很久才學會)
\*本篇文章大量參考[這裡](https://www.luogu.com.cn/article/53by9ud1)，~~因為是我學的地方~~，非常感謝作者大佬
- 舞蹈鍊是幹嘛的
舞蹈鍊最主要解決的問題是***精確覆蓋問題***，``在各個子集合中選擇若干個使其包含整個全集，並且各個子集合不重疊``，~~[上維基百科](https://zh.wikipedia.org/wiki/%E7%B2%BE%E7%A1%AE%E8%A6%86%E7%9B%96%E9%97%AE%E9%A2%98)~~,畫個圖就是這樣
要選擇其中幾行，使每一列都有一個$1$，並且選擇的行中，有$1$的列不能重疊
[模板題](https://www.luogu.com.cn/problem/P4929)
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實作
---
題目以[上面的模板題](https://www.luogu.com.cn/problem/P4929)做舉例
- 先看變數
```cpp=
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``用於加點
- 初始化
```cpp=
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``也就是行可以先不處理，因為他不是真實的點。
處理完圖會長這樣子
- 增加節點
```cpp=
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``陣列，應該不難理解，這裡就不上圖了~~因為我懶~~，如果真的不行可以自己畫畫看
- 刪除一列
```cpp=
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``裡刪除，等同於刪除了這一列，但我們還要去枚舉刪除同在這一列的集合(行)，因為不能重複覆蓋，只刪除上下指標，代表從候選集合中刪除，但還是保留左右指標，確保同一集合連在一起，以便後續回溯復原
畫的有點~~超~~亂，希望看得懂
- 復原一列
```cpp=
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)
```cpp=
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)
```cpp=
#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，~~那推[我學的地方](https://www.luogu.com.cn/article/53by9ud1)~~，如果這篇文章有任何問題，歡迎來[我的DC](https://discord.gg/TTWbRQ9bTy)提出(~~沒有問題也可以來找我聊天~~)
Sign in with Wallet
Connect another wallet