欧拉路径、回路、图

前言

当一手标题党，快乐~

之前一直分不清楚，写篇笔记分辨一下。

欧拉路径

可以一笔画的路径，称为欧拉路径。不要求起点终点为同一点。

判定：

• 有向图：图中只有一个出度比入度大 \(1\) 的点（起点），与一个入度比出度大 \(1\) 的点（终点），其余点出入度相等。
• 无向图：图中只有两个奇点（起点和终点），其余点都是偶点。

当然，将有向边视作无向边后，路径必须连通。

欧拉回路

在欧拉路径的基础上，起点终点是同一点。

判定：

• 有向图：所有点的出入度相等。
• 无向图：所有点都是偶点。

欧拉图

• 欧拉图：具有欧拉回路的图。
• 半欧拉图：存在欧拉路径、但没有欧拉回路的图。

判断方法

判断一个图是否有欧拉路或欧拉回路，要用到 Fleury 算法。（虽然这不是文章的重点，重点是上文）

用 DFS 实现。

算法核心：除非都是桥，否则走桥边。

P7771 【模板】欧拉路径

code

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int MAXN=1e5+5;

int n,m;
int tmp[MAXN];
int rd[MAXN],cd[MAXN];
stack<int> st;
vector<int> G[MAXN];

void dfs(int S)
{
    for(int i=tmp[S];i<G[S].size();i=tmp[S])
        tmp[S]=i+1,dfs(G[S][i]);
    // tmp[S] : G[S][1,2,...,tmp[S]-1] 都已访问，下一次从 G[S][tmp[S]] 开始
    st.push(S);
}

signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1,u,v;i<=m;i++)
    {
        scanf("%lld%lld",&u,&v);
        G[u].push_back(v); // 注意有向图
        cd[u]++,rd[v]++;
    }
    for(int i=1;i<=n;i++) sort(G[i].begin(),G[i].end());
    int S=1,c1=0,c2=0;
    bool flg=1; // 是否所有点出入度相等
    for(int i=1;i<=n;i++)
    {
        if(cd[i]!=rd[i])
        {
            flg=0;
            if(cd[i]-rd[i]==1) c1++,S=i; // 出度比入度大 1
            else if(rd[i]-cd[i]==1) c2++;
            else return puts("No"),0;
        }
    }
    if(flg==0&&!(c1==c2&&c1==1))
        return puts("No"),0; // 不满足判定条件
    dfs(S);
    while(!st.empty())
        printf("%lld ",st.top()),st.pop();
    return 0;
}