1.題意

鏈接: 原題鏈接.

給你一個(gè)1~n全排列A，讓你判斷能否通過一種操作使之變?yōu)槟繕?biāo)排列B。該操作是：交換與當(dāng)前下標(biāo)i相距$d_i$的2個(gè)元素。
如：下標(biāo)為5,$d_5=2$，那么可以將下標(biāo)為5處的元素和下標(biāo)為3或7處的元素交換。

2.思路

從圖的角度思考，假如下標(biāo)為a處可以到達(dá)下標(biāo)為b處，那么就從a向b連一條有向邊，我們發(fā)現(xiàn)交換是相互的，故可以把這條有向邊改成無向邊。
我們進(jìn)一步發(fā)現(xiàn)想讓下標(biāo)為i的數(shù)變?yōu)?span id="ze8trgl8bvbq" class="katex--inline">$a_i$，而$a_i$在下標(biāo)j，那么只要從i到j(luò)有路徑就可以了。
那么是否只要對(duì)于每個(gè)下標(biāo)i，其與目標(biāo)排列的$a_i$所在下標(biāo)j間連通，就一定存在一種合理交換方案得到目標(biāo)排列？
答案是肯定的，構(gòu)造方法類似于拓?fù)渑判?#xff0c;在每個(gè)連通塊中，先找到度為1的點(diǎn)，把對(duì)應(yīng)元素移動(dòng)過去，然后去掉唯一的一條邊，循環(huán)進(jìn)行，可得出一定有解。（一個(gè)連通塊，按照topo序刪點(diǎn)，剩下的模塊依舊是一個(gè)連通塊）
由于本題只需要判斷真假，故只需要判斷目標(biāo)下標(biāo)和原下標(biāo)的連通性即可，這可以使用并查集或者floodfill算法，如下代碼用的是后者。（啊，，比賽的時(shí)候并查集都忘了該咋寫了~）

3.代碼

#include <iostream>using namespace std;const int N=110;bool g[N][N]; int n; int a[N],d[N],con[N]; bool st[N]; int cnt;void dfs(int u) {st[u]=true;con[u]=cnt;for(int i=0;i<n;i++){if(g[u][i]&&!st[i]){dfs(i);}}return; }void floodfill() {for(int i=0;i<n;i++){if(!st[i]){cnt++;dfs(i);}} }bool check() {for(int i=0;i<n;i++)if(con[a[i]-1]!=con[i])return false;return true; }int main() {cin>>n;for(int i=0;i<n;i++)cin>>a[i];for(int i=0;i<n;i++)cin>>d[i];for(int i=0;i<n;i++){if(d[i]+i<n){g[i][i+d[i]]=1;g[i+d[i]][i]=1;}if(i-d[i]>=0){g[i][i-d[i]]=1;g[i-d[i]][i]=1;}}floodfill();if(check())cout<<"YES\n";else cout<<"NO\n";}

4.收獲

當(dāng)遇到比較復(fù)雜的題目，考慮用圖論的角度思考問題

拓?fù)湫虻膬?yōu)秀性質(zhì)——一個(gè)連通塊，按照topo序刪點(diǎn)，剩下的模塊依舊是一個(gè)連通塊。誒呦，不錯(cuò)喲~

總結(jié)

以上是生活随笔為你收集整理的#ACW 4084 号码牌（无向图连通性+简单拓扑序）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。