我在洛谷的第十二篇article

bwsl · 2024-08-25 08:51:41 · 算法·理论

欧拉路径

目录链接

Fleury算法

Fleury算法用于解决欧拉回路的具体输出问题，在算法开始之前，我们先用一个dfs来判断这个图是否是一个连通块，然后再判断这个图中有奇数出度的点是否只有0个或2个，如果是0个或2个，则存在欧拉回路，如果是两个，则存在欧拉回路，对于欧拉回路，我们任意选择一个点作为dfs的第一个点，对于欧拉路径，我们选取两个奇数出度的点中之一来作为dfs的第一个点

我们在求取的时候，用栈这种数据结构

定义

欧拉路径是图中经过所有边恰好一次的路径，也就是一笔画。如果这条路径的起点和终点相同，则称为欧拉回路。具有欧拉回路的图称为欧拉图‌。

性质‌：

欧拉图中所有顶点的度数都是偶数。也就是说，图中存在欧拉回路的充要条件是图中每个结点的度数都是偶数。因为欧拉回路定义只能经过每条边一次，所以对于每一个节点，至少需要有2n(n=0,1……)条边连接该节点‌。

判定条件‌：

对于无向图，如果图中恰好存在两个点的度数是奇数，其余节点的度数为偶数，这两个度数为奇数的点即为欧拉路径的起点和终点；如果图中所有点的度数都是偶数，则存在欧拉回路。对于有向图，如果图中恰好存在一个点的出度比入度多1，一个点的入度比出度多1，其余节点的出度和入度相等，则存在欧拉路径；如果所有点的入度和出度都相等，则存在欧拉回路‌。

欧拉路径代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;

int n,m,u,v,cd[N],rd[N],del[N],cnt1,cnt2;
vector<int> vec[N];
stack <int> s;
bool check;

void dfs(int x) {
    for(int i=del[x]; i<vec[x].size(); i=del[x]) {
        del[x]=i+1;
        int to=vec[x][i];
        dfs(to);
    }
    s.push(x);
}

int main() {
    cin>>n>>m;
    for(int i=1; i<=m; i++) {
        cin>>u>>v;
        vec[u].push_back(v);
        cd[u]++;
        rd[v]++;
    }
    for(int i=1; i<=n; i++) {
        sort(vec[i].begin(),vec[i].end());
    }
    int start=1;
    check=true;
    for(int i=1; i<=n; i++) {
        if(cd[i]!=rd[i]) {
            check=false;
            if(cd[i]-rd[i]==1) cnt1++,start=i;
            else if(rd[i]-cd[i]==1) cnt2++;
            else {
                cout<<"No";
                return 0;
            }
        }
    }
    if(!(cnt1==1&&cnt2==1)&&(!check)) {
        cout<<"No";
        return 0;  
    }
    dfs(start);
    while(!s.empty()) {
        cout<<s.top()<<" ";
        s.pop();
    }
    return 0;
}