CF1494F Delete The Edges 题解

Description

给定一张 $n$ 个点、$m$ 条边的图，你可以从图上任意一点出发，目标是删去所有的边，当一条边被删去后你不能再走此边。

初始模式下，一条边在你走过后会立即被删去。

你可以在任意一点切换模式（或全程不换），换完模式后走过的第偶数条便会被删去，且不可重新换回初始模式。

求一组方案。

Solution

观察样例可得切换模式后走的图为一个菊花图，下面浅浅分析一下。

假设只有一条边，则折返走一遍便能删完。

若为两条边 $(i,j),(j,k)$，发现只能 $j\to i\to j\to k\to j$ 将其删完。

依此类推，删边必须像 $i\to j\to i$ 折返地删。

所以我们可以枚举菊花图的中心，构造出走一条终点为菊花图中心的欧拉路径，然后切换模式的方案。

关键在于如何求出这条欧拉路径。

首先将所有和中心相连的奇点（度数为奇）和中心连的这条边删去，这样这个点就会变为偶点（度数为偶），方便后续操作。

然后得出当前图中奇点个数 $cnt$，和中心度数是否为 $0$，记为 $f$。

若 $f=true$：

• $cnt>2$，无法构出欧拉路径，非法。

• $cnt=2$ 且中心不为奇点，终点不为中心，非法。

• $cnt=2$ 且外围图不连通（除去度数为 $0$ 的点，这些点虽然不连通，但切换模式后都会连通），非法。

• $cnt=2$ 且外围连通，即我们已经构造出了合法方案。

若 $f=false$：

• $cnt\ge 2$，还要连一条边到中心，然而再加边就不是欧拉路径了，非法。

剩下还剩当前路径有中心但外围不连通、当前路径不含中心两种情况，发现 $cnt=0$ 使得我们可以在加一条删去的边到欧拉路径上，那我们就枚举这条边。

首先当前外围图（此时是除去度数为 $0$ 的点但此点不为中心）连通块个数要小于等于 $2$，因为加一条边只能让两个连通块连通。

然后分别将这两连通块染色，遍历删去的边，若边的两顶点颜色不同，则加上这条边，发现这种合法方案的起点就是这两顶点中不是中心的那个点。

发现一定存在这条先前被删去的边，即我们一定能找到合法方案。

然后我们按输出要求输出方案即可，首先遍历欧拉路径，再切换模式，然后折返删菊花图。

代码细节很多，理清思路再写。

时间复杂度 $O(n(n+m))$

Code

#include<bits/stdc++.h>
using namespace std;
int n,m;
int tot,head[3030];
int in[3030],du[3030],col[3030];
bool vis[3030],viss[3030],pit[3030];
vector<int> path;
struct edge{
	int to,next,id;
}e[6060];
void add(int x,int y,int z){
	e[++tot]=edge{y,head[x],z};
	head[x]=tot;
}
void dfs(int x,int v=0){
	viss[x]=1;
	col[x]=v;
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].to,w=e[i].id;
		if(viss[y]||vis[w]) continue;
		dfs(y,v);
	}
}
void get(int x){
	bool f=0;
	int ss,ww;
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].to,w=e[i].id;
		if(!vis[w]){
			vis[w]=1;
			get(y);
			path.push_back(x);
		}
	}
}
bool solve(int st){
	for(int i=1;i<=n;i++) du[i]=in[i],viss[i]=0,pit[i]=0,col[i]=0;
	for(int i=1;i<=m;i++) vis[i]=0;
	bool f=0;
	int ts=0,ttot=0;  //ts为方案起点、ttot为切换模式后删的边数
	for(int i=head[st];i;i=e[i].next){
		int y=e[i].to,w=e[i].id;
		if(du[y]%2){  //删去中心与偶点相连的边
			pit[y]=1,du[y]--,du[st]--,vis[w]=1,ttot++;
		}else f=1;  //中心是否在当前欧拉路径上
	}
	int cnt=0,fl=0;
	for(int i=1;i<=n;i++){
		if(du[i]%2) cnt++;  //奇点数量
		if(du[i]%2&&i!=st) fl=i;  //得出合法欧拉路径的起点
	}
	if(f){
		if(fl==0) fl=st;  //欧拉回路则任选起点
		if(cnt>2) return 0;
		if(cnt==2&&du[st]%2==0) return 0;
		if(cnt==2){
			dfs(st);
			for(int i=1;i<=n;i++){  //判断外围连通性
				if(du[i]==0) continue;
				if(!viss[i]) return 0;
			}
			ts=fl;
		}
		
	}else{
		if(cnt>=2) return 0;
	}
	if(cnt==0){
		dfs(st);  //染第一个连通块
		bool ff=0;
		for(int i=1;i<=n;i++){
			if(du[i]==0) continue;
			if(!viss[i]){
				if(ff) return 0;  //有至少三个连通块
				dfs(i,1);
				ff=1;
			}
		}
		if(ff){
			for(int i=head[st];i;i=e[i].next){
				int y=e[i].to,w=e[i].id;
				if(pit[y]&&col[y]){  //是之前删去的奇点且与中心不在同一连通块上
					pit[y]=0,vis[w]=0,ttot--;
					ts=y,du[y]++,du[st]++;
					break;
				}
			}
		}else{  //只有一个连通块即为欧拉回路
			ts=st;
		}
	}
	cout<<m+ttot+2<<'\n';  //m条边要删完则有m次操作，ttot条边被操作2次，加上起点和切换模式的2次操作
	get(ts);  //遍历欧拉路径
	for(int i=path.size()-1;i>=0;i--) cout<<path[i]<<" ";
	cout<<st<<" ";
	cout<<-1<<" ";
	for(int i=head[st];i;i=e[i].next){
		int y=e[i].to,w=e[i].id;
		if(pit[y]){
			cout<<y<<" "<<st<<" ";  //折返删菊花图
		}
	}
	return 1;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		in[x]++,in[y]++;
		add(x,y,i),add(y,x,i);
	}
	for(int i=1;i<=n;i++){
		if(solve(i)){
			return 0;
		}
	}
	cout<<"0"<<'\n';  //无解
	return 0;
}