07-31 02:02 阅读 108

关注

找欧拉回路为什么要回溯的时候存？

找欧拉回路为什么要回溯的时候存？

由题可知，优先选字典序小的字符
例如：

此时有两个奇点 aa 和 bb
优先选 aa
若正序保存
则序列为

a,b,c,da,b,c,d

显然这不是正解
则回溯的时候存

则序列为

b,d,c,ab,d,c,a

reversereverse 一下

a,c,d,ba,c,d,b

正确✔
为何？
因为：

#include<bits/stdc++.h>using namespace std;int n,head;char a[2];int b[130][130];//存图int deg[130],fa[130];//deg存储度数，fa存储父亲，用来并查集判断是否联通char ans[1330];//稍大于51*52/2int find(int x) {	if(fa[x]==x)return x;	return fa[x]=find(fa[x]);
}void dfs(int x) { //找欧拉回路/路径
	for(int i=64; i<=125; i++)		if(b[x][i]) {
			b[x][i]=b[i][x]=0;
			dfs(i);
		}
	ans[n--]=x;//因为是回溯的时候存，所以倒着存!!!!!!!}int main() {	cin>>n;	for(int i=64; i<=125; i++)fa[i]=i;	//A在ASCII码表里为65，z为122，所以64~125就足够了
	for(int i=1; i<=n; i++) {		cin>>a;
		b[a[0]][a[1]]=b[a[1]][a[0]]=1;
		deg[a[0]]++;
		deg[a[1]]++;		int xx=find(a[0]),yy=find(a[1]);
		fa[xx]=yy;
	}	int cnt=0;	for(int i=64; i<=125; i++)		if(fa[i]==i&&deg[i])cnt++;//祖宗结点
	if(cnt!=1) {		cout<<"No Solution"<<endl;    //如果不是连通图
		return 0;
	}
	cnt=0;
	head=0;	for(int i=64; i<=125; i++) {		if(deg[i]&1) {
			cnt++;			if(head==0)head=i;//顺道存储起点
		}
	}	if(cnt&&cnt!=2) {		cout<<"No Solution"<<endl;		return 0;
	}	//如果有奇数度数的点，并且不是两个，说明不存在欧拉回路/路径
	if(head==0)//如果是欧拉回路
		for(int i=64; i<=125; i++)			if(deg[i]) {
				head=i;    //找欧拉回路的起点
				break;
			}
	dfs(head);	cout<<ans;	return 0;
}

来源https://www.cnblogs.com/zhangshaojia/p/15082780.html