[省選聯考 2025] 圖排列 題解
閑話
一想到考場上自己以為直接輸出最小 dfn 序就有 \(52pts\) 我就想笑。
洛谷題解區有一個碼量小的分討做法，但是因為我不想分討所以還是選擇了這個實現起來不太用腦子的做法（雖然思路很需要腦子）。
題解
跟著部分分做。
題意
先把題面翻譯的人話一點：給定一張圖，要求字典序最小的排列 \(p\) 滿足對于 \(a<b<c<d\) 不能同時存在邊 \((p_a,p_c),(p_b,p_d)\)，換句話說就是按照這個排列的順序把點排好之后不能存在在除了端點之外的地方相交的邊。
樹
顯然 dfn 序一定合法，但這不一定最優。
首先我們肯定會把 \(1\) 放在第一位，然后考慮 \(1\) 的每棵子樹，顯然每棵子樹都是占據一段連續的區間，任意兩棵子樹占據的位置不會相交，否則必然會出現相交的邊。而兩棵子樹之間的順序是任意的。
然后每棵子樹就是一個獨立的子問題了，我們在求出每棵子樹的答案序列之后需要給這些子樹分配區間，那顯然就是按照第一個數從小到大排。
當然，我們在處理子問題的時候，假設處理的是 \(u\) 這棵子樹，那么 \(u\) 不一定是像 \(1\) 這樣放在第一個位置的，實際上 \(u\) 插在他的兒子子樹之間的任意空隙都是可以的。
所以直接把 \(u\) 作為一個長度為 \(1\) 的答案序列扔進去一起排序即可。
Tip：實際上 \(u\) 子樹的答案序列的第一個數一定是 \(u\) 子樹中編號最小的點，但是不知道這一點也問題不大，無非就是寫這檔分的時候可以簡單一點。
簡單環
對于一個環 \(x_1,x_2,x_3,...,x_k\)，環上的點在排列中的相對順序一定是這個環的某個循環，換句話說如果我欽定了 \(x_1\) 是排列中最靠前的點，那么其他點在排列中的相對順序只能是 \(x_2,x_3,..,x_k\) 或者 \(x_k,x_{k-1},...,x_2\)。
仙人掌
會了樹之后，對于一般圖我們顯然也希望可以套用樹的做法，圓方樹就可以很好地幫我們把圖轉換成樹的形態，所以我們不妨先考慮仙人掌的情況。
首先以 \(1\) 為根建出圓方樹：
對于一個圓點，他的兒子是方點，這些方點的子樹同樣需要滿足各自占領一段連續的區間，但是子樹之間是可以任意排列的，所以遞歸處理之后套用樹的做法即可。
對于一個方點，他代表了一個點雙，由于是仙人掌，這里一個點雙就是一個簡單環。這個環上的點就不能隨便亂排了，需要滿足我們上面環的要求。但是這還不夠，注意到這個方點存在一個父親圓點，這個環上的其他圓點要么全都放在這個父親之后，要么全都放在這個父親之前，因此這個方點的兒子總共只有兩種排列方法，一種正著放，一種反著放，取一個字典序最小的即可。
注：不管這些兒子圓點是放在父親之前還是之后，這兩種放法都是合法的，所以當前方點的決策并不依賴于父親的決策。
一般連通圖
現在一個點雙并不一定是一個簡單環了，但是題目保證了一定有解，所以可以想到這個點雙應該不會很復雜，考慮分析一下這題中點雙的性質：
結論一： 這個點雙不能存在同胚于 \(K_4\) 的子圖。也即這個點雙是廣義串并聯圖。
證：對于下面這個 \(K_4\)，顯然 \(1-2-3-4\) 和 \(1-2-4-3\) 這兩個環不可能同時滿足條件。
結論二： 這個點雙不能存在同胚于下面這個圖的子圖。
證：這個圖有三個環 \(1-2-3-4\)，\(1-2-3-5\)，\(1-4-3-5\)，我們枚舉第一個環在排列上的擺放方式（共有 \(8\) 種，但是 \(1,3\) 放在開頭的情況對稱，\(2,4\) 放在開頭的情況堆成，所以只枚舉 \(4\) 種）：
- \(1-2-3-4\)：第二個環只能是 \(1-2-3-5\) 或者 \(5-1-2-3\)，第三個環只能是 \(1-5-3-4\)，顯然不能同時合法。
- \(1-4-3-2\)：第二個環只能是 \(1-5-3-2\)，第三個環只能是 \(1-4-3-5\) 或者 \(5-1-4-3\)，顯然不能同時合法。
- \(2-3-4-1\)，\(2-1-4-3\)：同理，讀者自證不難。
根據這兩個結論可以知道這個點雙形如一個圓，然后圓上有一些弦，任意兩條弦不在除了頂點處相交。
所以這個點雙的哈密爾頓回路存在且唯一，就是最外面的圓，這個回路同樣需要滿足上面簡單環的限制。
我們只需要對每個點雙求出哈密爾頓回路就可以套用仙人掌的做法了，一種經典求法是像廣義串并聯圖那樣每次縮二度點疊重邊，然后在縮二度點的時候用鏈表維護哈密爾頓環，當然你也可以用 這篇題解 的做法。下面的代碼里寫的是前者。
一般圖
我們先對每個連通塊求出答案。
然后不難證明任意兩個連通塊在最終的答案序列上的區間要么不交，要么完全包含，即我們可以在某個連通塊的答案序列中插入另一個連通塊的完整的答案。
所以我們把所有連通塊的答案按照第一個數排序，從第一個連通塊開始填，當我即將要填的數大于下一個連通塊的第一個數時，就跳到下一個連通塊去做，做完了再繼續填當前連通塊的數。
復雜度 \(O(n)\) 或者 \(O(n\log n)\)。
code
貼一下用了一堆 STL 的巨大常數代碼（但是跑進 \(2s\) 還是沒問題的）。
點擊查看代碼
#include<bits/stdc++.h>
#define Debug puts("-------------------------")
#define eb emplace_back
#define PII pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=2e5+5;
inline int read(){
int w=1,s=0;
char c=getchar();
for(;c<'0'||c>'9';w*=(c=='-')?-1:1,c=getchar());
for(;c>='0'&&c<='9';s=s*10+c-'0',c=getchar());
return w*s;
}
int c,T,n,m;
int dfn[N],low[N],st[N],top,l[N];
bool vis[N];
vector<int> G[N],E[N];
vector<vector<int> > res;
namespace Solve{
int rt,num,cnt,fa[N],mn[N];
int pre[N],nxt[N],deg[N],id[N];
vector<int> res,dcc[N];
set<int> S[N];
set<PII> lst;
void init(){
for(int i=1;i<=cnt;i++) dcc[i].clear();
top=num=cnt=0;
res.clear();
}
void dfs0(int u,int fa){
vis[u]=true;
dfn[u]=low[u]=++num,st[++top]=u;
for(int v:G[u]){
if(v==fa) continue;
if(!dfn[v]){
dfs0(v,u),low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]){
int x; ++cnt,E[n+cnt].clear();
do{
x=st[top--];
dcc[cnt].eb(x),E[n+cnt].eb(x),E[x].eb(n+cnt);
}while(x!=v);
dcc[cnt].eb(u),E[n+cnt].eb(u),E[u].eb(n+cnt);
}
}
else low[u]=min(low[u],dfn[v]);
}
}
void dfs1(int u,int Fa){
fa[u]=Fa;
if(Fa) E[u].erase(find(E[u].begin(),E[u].end(),Fa));
for(int v:E[u]) dfs1(v,u);
}
void solve(){
if(lst.size()==2){
int u=(*lst.begin()).se,v=(*lst.rbegin()).se;
nxt[u]=pre[u]=v,nxt[v]=pre[v]=u;
return;
}
int u=(*lst.begin()).se,x,y; lst.erase(lst.begin());
x=*S[u].begin(),y=*S[u].rbegin();
S[x].erase(S[x].find(u)),S[y].erase(S[y].find(u));
if(!S[x].count(y)) S[x].insert(y),S[y].insert(x);
else{
lst.erase({deg[x],x}),lst.erase({deg[y],y});
deg[x]--,deg[y]--,lst.insert({deg[x],x}),lst.insert({deg[y],y});
}
solve();
if(nxt[x]==y) nxt[x]=pre[y]=u,pre[u]=x,nxt[u]=y;
else pre[x]=nxt[y]=u,nxt[u]=x,pre[u]=y;
}
void Get_Hamiltonloop(int c){
lst.clear();
for(int u:dcc[c]) id[u]=c;
for(int u:dcc[c]){
pre[u]=nxt[u]=u,deg[u]=0,S[u].clear();
for(int v:G[u]) if(id[u]==id[v]) S[u].insert(v),deg[u]++;
lst.insert({deg[u],u});
}
solve();
int x=nxt[fa[n+c]],t=fa[n+c];
dcc[c].clear(),dcc[c].eb(t);
while(x!=t) dcc[c].eb(x),x=nxt[x];
}
void dfs2(int u){
if(!E[u].size()) return mn[u]=u,void();
for(int v:E[u]) dfs2(v);
if(u<=n){
sort(E[u].begin(),E[u].end(),[&](int x,int y){return mn[x]<mn[y];});
mn[u]=min(u,mn[E[u][0]]);
}
else{
E[u].clear();
int c=u-n;
if(mn[dcc[c][1]]<mn[dcc[c].back()]) for(int i=1;i<dcc[c].size();i++) E[u].eb(dcc[c][i]);
else for(int i=dcc[c].size()-1;i>=1;i--) E[u].eb(dcc[c][i]);
mn[u]=mn[E[u][0]];
}
}
void dfs3(int u){
if(u>n) for(int v:E[u]) dfs3(v);
else{
bool flag=false;
for(int v:E[u]){
if(mn[v]>u&&!flag) res.eb(u),flag=true;
dfs3(v);
}
if(!flag) res.eb(u);
}
}
vector<int> work(){
init();
if(G[rt].size()==0){
vis[rt]=true;
return {rt};
}
dfs0(rt,0),dfs1(rt,0);
for(int i=1;i<=cnt;i++) Get_Hamiltonloop(i);
dfs2(rt),dfs3(rt);
return res;
}
}
void Init(){
res.clear();
for(int i=1;i<=n;i++) G[i].clear(),E[i].clear(),vis[i]=dfn[i]=low[i]=0;
}
void work(){
Init();
n=read(),m=read();
for(int i=1;i<=m;i++){
int u=read(),v=read();
G[u].eb(v),G[v].eb(u);
}
int cnt=0,id=0;
for(int i=1;i<=n;i++) if(!vis[i]) Solve::rt=i,res.push_back(Solve::work()),l[cnt++]=0;
top=0;
st[++top]=id++;
while(top||id<cnt){
if(top==0) st[++top]=id++;
int i=st[top];
while(l[i]<res[i].size()&&(id==cnt||res[i][l[i]]<res[id][0])) printf("%d ",res[i][l[i]++]);
if(l[i]<res[i].size()) st[++top]=id++;
else top--;
}
puts("");
}
signed main(){
c=read(),T=read();
while(T--) work();
return 0;
}
浙公網安備 33010602011771號