题解：P10851 [EGOI2024] Make Them Meet / 活动面基

· · 题解

这篇题解爆了，只是它能通过官方数据（hack：有三个三元环套在一起）有没有人修一下做法

高明的图论构造题。

Make Them Meet / 活动面基

在某一轮中，称两个点被染上同一种颜色且它们在原图上有连边为“连边”。

对于一条链的构造

奇数轮连边 (1,2),(3,4),(5,6),\dots，偶数轮连边 (2,3),(4,5),(6,7),\dots。这样每个人会在链上不断循环走，经过 2n 轮后，两个人一定会相遇。

对于一棵树的构造

取任意一个节点为根，dfs 整棵树。

奇数轮连所有 dep 为奇数的点 u 到 fa_u 的边，偶数轮则连所有 dep 为偶数的点的父亲边。同时在每一轮中，都连上 (rt,son) 的边，其中 son 为 rt 的任意一个儿子。

容易发现，一个点可能先往下走到一个叶子再往上走，在走到 rt 之后就会一直在 (rt,son) 的边上不停循环。

这样在 2n 轮后，两个人一定会在 (rt,son) 的边上相遇。

对于一般图的构造

对于上述树的构造，我们发现只要满足以下的条件就能套用到图上：

考虑先建一棵 dfs 树，然后分类讨论。

若 dfs 树为一条链，则可直接套用链的做法。

否则，我们可以找到一个分叉点 u，使得 u 是最深的分叉点。则 u 的所有儿子子树都是链。

设 u 的父亲节点为 f。

若 u 有一个儿子 v 使得 v,f 没有连边，则可以从 v 开始重新求一棵 dfs 树，并且优先 dfs v\to u\to f \dots。这样 u 在新 dfs 树中的儿子只可能是 f 或 u 的其他儿子，v 与它们没有连边。取 rt=v,son=u 就构造完毕。

否则，u 的所有儿子都和 f 有连边。任意取一个儿子 v，从 v 开始重新求一棵 dfs 树，并且优先 dfs v\to u\to \{son_u\}，其中 \{son_u\} 为 u 的其他儿子。由于 u 的其他儿子与 f 有连边，所以原树在 f 之上的部分会在 u 的其他儿子下方被 dfs 到，不会成为新树中 u 的儿子。那么 v 与 u 的儿子没有连边，取 rt=v,son=u 构造完毕。

时间复杂度 O(n) 且操作次数为 2n 轮。

// what is matter? never mind. 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define int long long
#define ull unsigned long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 200006
#define inf 0x3f3f3f3f

int n,m,rt;
int e[105][105],deg[105];
vi g[105];

int fa[105],dep[105];
vi son[105];
vi que;

bool del[105];

void dfs(int u,int pa){
    que.pb(u);
    fa[u]=pa,dep[u]=dep[pa]+1;
    for(int v:g[u])
        if(v!=pa && !dep[v]) son[u].pb(v),dfs(v,u);
}
int col[maxn];

void chain(vi o){
    cout<<n*2<<"\n";
    For(i,1,n*2){
        For(j,0,n-1) {
            if((j&1)==(i&1) && j) col[o[j]]=o[j-1];
            else col[o[j]]=o[j];
        }
        For(u,1,n) cout<<col[u]<<" "; cout<<"\n";
    }
    exit(0);
}

void out(int rt,int dw){
    cout<<n*2<<"\n";
    For(t,1,n*2){
        For(i,1,n){
            if(i==rt) {
                if(t&1) cout<<dw<<" ";
                else cout<<rt<<" ";
            }else{
                if((t&1)==(dep[i]&1)) cout<<fa[i]<<" ";
                else cout<<i<<" ";
            }
        }
        cout<<"\n";
    }
    exit(0);
}

void dfs2(int u,int pa){
//  cout<<"Dfs2 "<<u<<" "<<pa<<" "<<dep[pa]<<"\n";
    fa[u]=pa,dep[u]=dep[pa]+1;
    for(int v:g[u])
        if(v!=pa && !dep[v] && !del[v]) dfs2(v,u);
}

vi g2[105];
void dfsc(int u,int pa){
    que.pb(u);
    for(int v:g2[u]) if(v!=pa) dfsc(v,u);
}

signed main()
{
    n=read(),m=read();

    For(i,1,m){
        int u=read(),v=read();
        ++u,++v;
        e[u][v]=e[v][u]=1;
        ++deg[u],++deg[v];
        g[u].pb(v),g[v].pb(u);
    }

    dfs(1,0);

    bool ok1=1;
    For(i,1,n)
        for(int v:son[i]) g2[i].pb(v),g2[v].pb(i);
    For(i,1,n) ok1&=(g2[i].size()<=2);
    if(ok1){
        int u=1;
        For(i,1,n) if(g2[i].size()==1) u=i;
        que.clear();
        dfsc(u,0);
        chain(que);
        exit(0);
    }

    int u=0;
    For(i,1,n) if(son[i].size()>1 && dep[i]>=dep[u]) u=i;
    int f=fa[u];
    if(!f){
        For(i,1,n) son[i].clear(),fa[i]=dep[i]=0; que.clear();
        int v=son[u][0];
        dfs(v,0);
        u=0;
        For(i,1,n) if(son[i].size()>1 && dep[i]>=dep[u]) u=i;
        f=fa[u];
        assert(f);
    }

    del[u]=1;
    for(int v:son[u])
        if(!e[v][f]) {
            g[v].insert(g[v].begin(),u);
            g[u].insert(g[u].begin(),f);
            For(i,1,n) son[i].clear(),fa[i]=dep[i]=del[i]=0; que.clear();
            dfs2(v,0);
            out(v,u);
            exit(0);
        }
//  assert(0);

    int v=son[u][0];
    for(int x:son[u])
        if(x!=v) g[u].insert(g[u].begin(),x);
    g[v].insert(g[v].begin(),u);
    For(i,1,n) son[i].clear(),fa[i]=dep[i]=del[i]=0; que.clear();
    dfs2(v,0);
    out(v,u);
    return 0;
}
/*

*/