自动搬运

查看原文

来自洛谷，原作者为

	Rainbow_qwq **

搬运于2025-08-24 23:01:51，当前版本为作者最后更新于2024-08-15 00:29:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这篇题解爆了，只是它能通过官方数据（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)$ 的边上相遇。

对于一般图的构造

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

• 对于任意一个点 $u$，$u$ 的所有儿子之间没有连边。（在给 $u$ 和儿子染同种颜色时不会走错）
• 对于根节点 $rt$，需要选出一个儿子 $son$，使得 $rt$ 和 $son$ 的所有儿子没有连边。（在给 $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;
}
/*

*/