怎么哪儿都有欧拉的事儿？！

想必各位小学时可能做过一种叫一笔画的题，就是任选一个起点，是否能够仅用一笔，走完所有路（有时可能还会加上要回到起点的要求）。
这就和这个笔记的内容有点关系了。

是什么

欧拉路就是指从图中某个点出发，遍历整个图，图中每条边通过且只通过一次的路径。
比如像这样：

欧拉回路就是起点和重点是同一个点的欧拉路径。
就是这样：

（五角星）

最后，欧拉图：具有欧拉回路的图。注意是回路。

一些条件

根据刚刚的图，你会发现一些东西：

无向图
无向图存在欧拉回路的充要条件 （高数吗有意思，高数：高中数学）：
当且仅当该图所有顶点度数都为偶数，且该图是连通图。

无向图存在欧拉路的条件：
只有两个奇点，一个是起点，一个是终点。

有向图
好像没图啊。

有向图存在欧拉回路的充要条件：
一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。

有向图存在欧拉路的条件：
恰好存在1个点出度比入度多1，1 个点入度比出度多1，其余节点出度等于入度。

怎么实现

1.欧拉路径

我们以有向图为例（单纯是应为板子题是有向图的）
首先，要存图吧，我喜欢用 vector 来存，同时记录一条边的起点、终点、和编号。

vector<pair<int,int> >g[N];
//第一个存中点，第二个存编号

输入时记录入读和出度（无向图只需要记录度数）：

for(int i=1,u,v;i<=m;i++){
    cin>>u>>v;
    g[u].push_back({v,i});
    in[v]++;
    out[u]++;//无向边只需要d[u]++,d[v]++
}

然后判断是否符合欧拉路径的标准，那我们只需要在入度和出度不同的时候判断。

• 先看差值是否为1；
• 然后数度数特殊的点的数量：
  • 有向图是将(out_i-in_i=1)和(in_i-out_i=1)分开来计数的。
  • 无向图只需要统计(d_i%2==1)的点的数量就行了。
• 最后判断是否符合有向图/无向图的要求，不符合直接无解。

bool f=1;
for(int i=1;i<=n;i++){//n表示点数
    if(in[i]==out[i]) continue;
    if(out[i]==in[i]+1) s=i,cst++;
    else if(out[i]==in[i]-1) ced++;
    else{
        f=0;
        break;
    }
}
if(!f||!(cst==0&&ced==0||cst==1&&ced==1)) return cout<<"No",0;
//无向边时，只需要if(d[u]&1) cnt++;
//然后if(cnt>2) return cout<<"No",0;

我还加了一个如果该图是欧拉图（是欧拉回路）的找起点的：

if(cst==0&&ced==0)
    for(int i=1;i<=n;i++)
        if(g[i].size()){
            s=i;
            break;
        }

接着dfs找路径，这里用了一个当前弧优化：

stack<int> st;
void dfs(int u){
    for(int i=cur[u];i<g[u].size();i=cur[u]){
        cur[u]=i+1;
        if(flg[g[u][i].__]) continue;
        flg[g[u][i].__]=1;
        dfs(g[u][i]._);
    }
    st.push(u);
}
//_表示first，__表示second。
//详情见代码实现的宏定义

最后，先判一下图是否连通，不连通的话 dfs 只会跑一部分，跑不全。

if(st.size()!=m+1) return cout<<"No",0;//m表示边数

输出。

while(st.size()){
    cout<<st.top()<<" ";
    st.pop();
}

代码实现

PID:P7771（这是板子题）

#include<bits/stdc++.h>
#define int long long
#define _ first
#define __ second
using namespace std;
const int N=2e5+10;
int n,m,cur[N],in[N],out[N],s=1,cst,ced;
bool flg[N],f=1;
vector<pair<int,int> > g[N];
stack<int> st;
bool cmp(pair<int,int> a,pair<int,int> b){return a._<b._;}
void dfs(int u){
	for(int i=cur[u];i<g[u].size();i=cur[u]){
		cur[u]=i+1;
		if(flg[g[u][i].__]) continue;
		flg[g[u][i].__]=1;
		dfs(g[u][i]._);
	}
	st.push(u);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1,u,v;i<=m;i++){
		cin>>u>>v;
		g[u].push_back({v,i});
		in[v]++;
		out[u]++;
	}
	for(int i=1;i<=n;i++) sort(g[i].begin(),g[i].end(),cmp);
	for(int i=1;i<=n;i++){
		if(in[i]==out[i]) continue;
		if(out[i]==in[i]+1) s=i,cst++;
		else if(out[i]==in[i]-1) ced++;
		else{
			f=0;
			break;
		}
	}
	if(!f||!(cst==0&&ced==0||cst==1&&ced==1)) return cout<<"No",0;
	if(cst==0&&ced==0) for(int i=1;i<=n;i++)
		if(g[i].size()){
			s=i;
			break;
		}
	dfs(s);
	if(st.size()!=m+1) return cout<<"No",0;
	while(st.size()){
		cout<<st.top()<<" ";
		st.pop();
	}
	return 0;
}

感觉不是很难