欧拉道路与欧拉回路

欧拉道路是指不重复的经过图的每一条边所形成的道路

欧拉回路是指不重复的经过图的每一条边所形成的回路

这类问题都可以使用dfs来求解

下面给出几道例题

1.P6066 [USACO05JAN] Watchcow S

解析：

一道模板题，建好双向边，走过一次删掉一条

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+39+7;
int n,m,vis[N];
struct node{
	int to,visit;
};
stack<int>st;
vector<node>G[N]; 
void dfs(int x){
	for(int i=vis[x];i<G[x].size();i=vis[x]){
		vis[x]=i+1;
		if(G[x][i].visit)continue;
		G[x][i].visit=1;
		dfs(G[x][i].to);
	}
	st.push(x);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;cin>>x>>y;
		G[x].push_back({y,0});
		G[y].push_back({x,0});
	}
	dfs(1);
	while(st.size()){
		cout<<st.top()<<'\n';
		st.pop();
	}
	return 0;
}

2.P7771 【模板】欧拉路径

解析：

模板题，判断有向图是否存在欧拉路径，只需要看度，如果存在入度和出度不等的，判断一下，分三种情况：1.入度-出度=1，cnt++ 2.出度-入度=1，cnt1++，并将起点设为当前点的编号  3.直接输出No

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+39+7;
vector<int>G[N];
stack<int>st;pair<int,int>cnt={0,0};
int n,m,vis[N],din[N],dout[N],is=1,s=1;
void dfs(int x){
	for(int i=vis[x];i<G[x].size();i=vis[x]){
		vis[x]=i+1;
		dfs(G[x][i]);
	}
	st.push(x);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;cin>>x>>y;
		G[x].push_back(y);
		din[y]++;dout[x]++;
	}
	for(int i=1;i<=n;i++)sort(G[i].begin(),G[i].end());
	for(int i=1;i<=n;i++){
		if(din[i]!=dout[i]){
			is=0;
			if(din[i]-dout[i]==1)cnt.first++;
			else if(dout[i]-din[i]==1){
				cnt.second++;
				s=i;
			}else{
				cout<<"No";
				return 0;
			}
		}
	}
	if((!is)&&!(cnt.first==cnt.second&&cnt.first==1)){
		cout<<"No";
		return 0;
	}
	dfs(s);
	while(st.size()){
		cout<<st.top()<<' ';
		st.pop();
	}
	return 0;
}

3.P1341 无序字母对

解析：
使用字母编号跑欧拉路径的模版即可，编号规则：A~Z为1~26，a~z为27~52

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e3+39+7;
int calc(char c){
	if(c<='z'&&c>='a')return c-'a'+27;
	else return c-'A'+1;
}
char uncalc(int n){
	if(n>=27&&n<=52)return n+'a'-27;
	else return n+'A'-1;
}
int n,m,vis[N],d[N],a[N][N];
stack<int>st;
void dfs(int x){
	for(int i=1;i<55;i++){
		if(!a[x][i])continue;
		a[x][i]=a[i][x]=0;
		dfs(i);
	}
	st.push(x);
}
int main(){
	cin>>n;
	int k=0x3f3f3f3f;
	for(int i=1;i<=n;i++){
		string s;cin>>s;
		a[calc(s[0])][calc(s[1])]=a[calc(s[1])][calc(s[0])]=1;
		++d[calc(s[0])];++d[calc(s[1])];
		k=min(k,min(calc(s[0]),calc(s[1])));
	}
	int cnt=0,t=0x3f3f3f3f;
	for(int i=1;i<=55&&cnt<=2;i++){
		if(d[i]%2){
			cnt++;
			t=min(t,i);
		}
	}
	if(cnt==1||cnt>2){
		cout<<"No Solution";
		return 0;
	}
	if(cnt==0)dfs(k);
	else dfs(t);
	while(st.size()){
		cout<<uncalc(st.top());
		st.pop();
	}
	return 0;
}