P11832 [省选联考 2025] 图排列 题解
OccDreamer · · 题解
感觉挺有意思的。
首先我们可以对于
树
首先来考虑树的情况，对于给定的一棵树
我们首先令
那么我们划分
如果不这样划分那么肯定会出现
继续观察这样划分会有什么性质，以
所以我们可以选择一个
上述的方法肯定能够合法排布。
也就是说我们可以令
这样我们就可以构造出一棵树的解。
图
现在有了环该怎么办呢？
如果有一个环
我们令这一个环上在排列
所以我们将所有极大的简单环缩在一起，也就是跑点双连通分量。
然后考虑建圆方树，有了树的结构之后我们考虑修改一下树的做法。
首先对于每一个圆点而言，其所有儿子都是代表一个点双，这些点双的顺序和树的分析一样，可以任意排列，那么我们肯定取这一个点双中 能取到的最小的 第一个值来排序。
但是对于一个方点而言，儿子的顺序并不能随意排列，因为上面我们说了对于一个环其顺序只有两种可能，又因为这题保证有解，所以一个点双中不可能有两个不同的简单环。
证明如下
"
如果环中没有 "
如果有 "
通过缩二度点得到了每一个点双的简单环之后和树的做法就没有太大差别了。
连通块的整合也是容易的，一个连通块可以整体一起插入到某一个位置，处理出每一个连通块的答案之后贪心即可。
//Mashiro
#include<bits/stdc++.h>
#define vc vector
#define db double
#define fi first
#define se second
#define ll long long
#define mk make_pair
#define pb push_back
#define RI register int
#define PI pair<int,int>
#define ull unsigned long long
#define err cerr << " -_- " << endl
#define debug cerr << " ------------------- " << endl
#define input(x) freopen(#x".in","r",stdin)
#define output(x) freopen(#x".out","w",stdout)
#define NO puts("No")
#define YES puts("Yes")
//#define OccDreamer
//#define int long long
using namespace std;
namespace IO{
inline ll read(){
ll X=0, W=0; char ch=getchar();
while(!isdigit(ch)) W|=ch=='-', ch=getchar();
while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar();
return W?-X:X;
}
inline void write(ll x){
if(x<0) x=-x, putchar('-');
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline void sprint(ll x){write(x), putchar(32);}
inline void eprint(ll x){write(x), putchar(10);}
}using namespace IO;
const int MAXN = 2e5 + 2;
int n, m;
int stk[MAXN], fa[MAXN], topf;
int low[MAXN], dfn[MAXN], tim[MAXN], tot;
int head[MAXN], ne[MAXN<<1], to[MAXN<<1], mn[MAXN], node, cnt;
vc<PI> ed[MAXN];
vc<int> ans, G[MAXN], res[MAXN];
priority_queue<int> Q;
bool vis[MAXN];
inline bool comp(int x, int y){return mn[x]<mn[y];}
inline void add(int x, int y){++cnt;to[cnt]=y;ne[cnt]=head[x];head[x]=cnt;}
inline void tarjan(int x, int f){
dfn[x]=low[x]=++tot; stk[++topf]=x;
for(int i=head[x];i;i=ne[i]){
if(dfn[to[i]]){
if(to[i]^f) low[x]=min(low[x],dfn[to[i]]);
}
else{
tarjan(to[i],x), low[x]=min(low[x],low[to[i]]);
if(low[to[i]]>=dfn[x]){
++node; G[node].clear(); ed[node].clear();
G[x].pb(node); fa[node]=x; stk[topf+1]=0;
while(stk[topf+1]!=to[i]){
int t=stk[topf];
G[node].pb(t); fa[t]=node;
--topf;
}
}
}
}
return ;
}
inline void build(int x, int id, int f){
if(x^f) G[id].pb(x); vis[x]=1;
for(int i=head[x];i;i=ne[i]){
if(vis[to[i]]) continue;
build(to[i],id,f);
}
return ;
}
set<int> e[MAXN];
set<PI> E, ban;
queue<int> q;
int deg[MAXN];
inline void Run(int lim){
E.clear(); ban.clear();
while(q.size()){
int t=q.front(); q.pop();
if(e[t].size()==1 && E.size()<lim){
int x=*e[t].begin();
E.insert(mk(min(t,x),max(t,x)));
}
if(e[t].size()==2){
int x=*e[t].begin(), y=*e[t].rbegin();
e[x].insert(y);
e[y].insert(x);
ban.insert(mk(min(x,y),max(x,y)));
}
for(auto i:e[t]){
e[i].erase(e[i].lower_bound(t));
if(ban.find(mk(min(t,i),max(t,i)))==ban.end()){
E.insert(mk(min(t,i),max(t,i)));
}
if(e[i].size()==2) q.push(i);
}
e[t].clear();
}
for(auto i:E) add(i.fi,i.se), add(i.se,i.fi);
return ;
}
inline void rebuild(int x){
int cntt=0;
for(auto i:G[x]) ++cntt, vis[i]=0, head[i]=deg[i]=0; vis[fa[x]]=0; head[fa[x]]=deg[fa[x]]=0;
for(auto i:ed[x]) e[i.fi].insert(i.se), e[i.se].insert(i.fi), deg[i.fi]++, deg[i.se]++;
for(auto i:G[x]) if(deg[i]<=2) q.push(i);
if(deg[fa[x]]<=2) q.push(fa[x]);
G[x].clear(); Run(cntt);
return build(fa[x],x,fa[x]);
}
inline void DFS(int x, int f){
int minn=(x<=n?x:0);
for(auto i:G[x])
DFS(i,x), minn=min(minn,mn[i]);
if(x<=n){
G[x].pb(x); mn[x]=x;
sort(G[x].begin(),G[x].end(),comp);
mn[x]=minn;
}
else{
rebuild(x);
if(mn[G[x][0]]>mn[G[x].back()]) reverse(G[x].begin(),G[x].end());
mn[x]=mn[G[x][0]];
}
return ;
}
inline void getres(int x, int id){
vis[x]=1;
for(auto i:G[x]){
if(i==x) res[id].pb(x);
else getres(i,id);
}
return ;
}
inline void solve(int x){
DFS(x,0);
getres(x,x);
return ;
}
inline void work(int x){
for(auto i:res[x]){
int lmt=Q.empty()?n+1:-Q.top();
while(lmt<i){
Q.pop();
work(lmt);
lmt=Q.empty()?n+1:-Q.top();
}
sprint(i);
}
return ;
}
inline void solve(){
node=n=read(), m=read(); cnt=tot=topf=0;
for(int i=1;i<=n;++i) G[i].clear(), head[i]=dfn[i]=0;
for(int i=1;i<=m;++i){
int x, y;
x=read(), y=read();
add(x,y), add(y,x);
}
for(int i=1;i<=n;++i)
if(!dfn[i]) tarjan(i,fa[i]=0);
for(int i=1;i<=n;++i){
for(int j=head[i];j;j=ne[j]){
if(to[j]<i){
int x=to[j], y=i;
if(fa[x]==fa[y]) ed[fa[x]].pb(mk(x,y));
else{
if(fa[fa[x]]==y) ed[fa[x]].pb(mk(x,y));
else ed[fa[y]].pb(mk(x,y));
}
}
}
}
cnt=0;
for(int i=1;i<=n;++i) vis[i]=0, head[i]=0;
for(int i=1;i<=n;++i){
if(vis[i]) continue;
// cerr << "DFS:" << i << endl;
res[i].clear(); Q.push(-i);
solve(i);
}
while(!Q.empty()){
int t=Q.top(); Q.pop();
work(-t);
}
// int cur=3, las=-1;
// while(cur) {
// // cerr << cur << endl;
// las=cur; cur=fa[cur];
// if(cur==0) break;
// if(G[cur][0]==las || G[cur].back()==las) cerr << "GOOD" << endl;
// else cerr << "BAD" << endl;
// }
putchar(10);
}
int main(){
freopen("graperm.in","r",stdin);
freopen("graperm.out","w",stdout);
int c, t;
c=read(), t=read();
while(t--) solve();
return 0;
}
/*
0 1
10 11
3 6
4 9
1 7
9 6
6 7
1 9
2 3
7 8
2 8
2 6
7 10
*/