自动搬运

查看原文

来自洛谷，原作者为

	big_turkey 这只火鸡很蒻，什么也没有留下

搬运于2025-08-24 21:49:47，当前版本为作者最后更新于2020-11-22 10:02:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

2024/11/29 更新

题解又被人hack了，来补。

把原来存欧拉回路的空间上限增大了。

这里感谢 @chenxi2009 指出错误。

2021/10/18 更新

题解被人hack了，一年后过来补。

这里感谢 @fzj2007 提供的hack数据。

下面代码已通过LOJ的强数据和hack数据。

下面部分更新的地方都用粗体表示

题目分析

总共有m条边，走过一条边就是修改该边权值。

每次要求走过一个简单环上的边，即从某个点开始走过该点存在的联通图（原图可能不联通），初始权值与最终权值相等的边走偶数次，不相等的走奇数次。

为什么用欧拉回路？

• 欧拉回路的定义：存在一条从某个点开始，恰好不重不漏经过每条边一次（点可重复），最终回到该点。

• 欧拉图的定义：存在欧拉回路的图。

• 欧拉图的判定：每个点的度数都为偶数。

通过以上定义和判定，可以考虑权值不相等的边通过找欧拉回路的方法来。

权值相等的边，因为每次都必须走偶数次，相当于拆成了两条边，这样实际上就使得改边对连接的两点度数加了 +2，根据欧拉回路的定义，删去这条边即对两点度数 -2，还使得图成为欧拉图了（只用走剩下的边一次），就可以直接找欧拉回路了。

原代码没有处理不经过重复边或起点以外结点的环，即每次只能走以起点开始的环

这样的话，就可以再开一个栈专门来存当前的欧拉回路，如果当前的点已经在栈中，说明已经形成一个环，将该环储存答案并弹出。

代码细节处理

我原来的代码是用栈模拟 dfs 的搜索和回溯过程。

每次取栈顶元素，遍历其没有遍历过的边，将出点存入栈中。

遍历没有遍历过的边后要将链头都要指向下一条未遍历的边，以保证时间复杂度正确。

如果没有可遍历的出边，那么就应该回溯，将该点弹出并存入答案栈中，此时答案栈存入的即是以 $s$ 为起点能遍历完所有可到达的边的欧拉回路，可能包含除起点以外的环，所以存入时要判断是否形成环，成环时将答案处理。

代码

以下代码省去模板和一些简单的宏。

应该没问题吧

const ll maxn=1e5+5,maxm=1e6+5;

ll n,m,cnt=1,head[maxn];
ll deg[maxn];

ll tot;
vector<ll> ans[maxm];

ll stk[maxm],tp;
ll stkans[maxm],tpans;//存欧拉回路的答案栈
bool instk[maxm]；//标记是否在答案栈中
bool vis[maxm];

struct edge{
	ll to,next,vis;
}e[maxm<<1];

void add(ll x,ll y){
	e[++cnt]=(edge){y,head[x],0};
	head[x]=cnt;
	deg[x]++;
}

#define failed return puts("NIE"),0

void euler(ll s){
	stk[tp=1]=s;
	for(ll x,i;tp;){
		x=stk[tp],i=head[x];
		while(i&&e[i].vis) 
			head[x]=i=e[i].next;
		if(i){
			stk[++tp]=e[i].to;
			e[i].vis=e[i^1].vis=true;
			head[x]=e[i].next;//链头指向下一条边
		}
		else{
			tp--;
			vis[x]=true;
			if(instk[x]){
				ans[++tot].push_back(x);
				while(tpans&&stkans[tpans]!=x)
					ans[tot].push_back(stkans[tpans]),
					instk[stkans[tpans--]]=false;
				ans[tot].push_back(x);
			}
			else instk[stkans[++tpans]=x]=true;
		}
	}
}

void output(){
	printf("%lld\n",tot);
	FOR(i,1,tot){
		printf("%lld\n",ans[i].size()-1);
		for(auto x:ans[i]) printf("%lld ",x);
		puts("");
	}
}

int main(){
	n=read(),m=read();
	for(ll x,y,o,p;m;m--){
		x=read(),y=read(),o=read(),p=read();
		if(o^p) add(x,y),add(y,x);
	}
	FOR(i,1,n) if(deg[i]&1) failed;
	FOR(i,1,n) if(!vis[i]) euler(i);
	output();
	return 0;
}

如果有错误的地方，请私信我