洛谷 U308246：一笔画问题 ← 欧拉回路（dfs 或 bfs）

​【题目来源】
https://www.luogu.com.cn/problem/U308246

【题目描述】
如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。
输入一个无向图，根据一笔画的两个定理，如果寻找欧拉回路，对一号点执行深度优先遍历；找欧拉路，则对最后一个奇点执行 dfs，时间复杂度为 O(m+n)，m 为边数，n 是点数。

【输入格式】
第一行 n，m，有 n 个点，m 条边，以下 m 行描述每条边连接的两点。

【输出格式】
欧拉路或欧拉回路，输出一条路径即可。要求从小到大顺序搜索，如果有奇点从编号大的奇点开始，否则从 1 开始搜索，回溯时存储输出。

【输入样例】
5 5
1 2
2 3
3 4
4 5
5 1

【输出样例】
1 5 4 3 2 1

【数据范围】
对于 100% 的数据：1<n<100，1<m<2000。

【算法分析】
● 欧拉路径与欧拉回路定义
图中经过所有边恰好一次的路径称为欧拉路径（也就是一笔画）。
如果此路径的起点和终点相同，则称其为欧拉回路。
注意：若存在欧拉回路，则一定存在欧拉路径。

● 欧拉路径判定
（1）有向图欧拉路径：图中恰好存在 1 个结点的出度比入度多 1（这个结点即为起点 S），1 个结点的入度比出度多 1（这个结点即为终点 T），其余结点的出度=入度。
（2）有向图欧拉回路：所有结点的入度=出度（起点 S 和终点 T 可以为任意点）。
（3）无向图欧拉路径：图中恰好存在 2 个结点的度是奇数，其余结点的度为偶数，这两个度为奇数的结点即为欧拉路径的起点 S 和终点 T。
（4）无向图欧拉回路：所有结点的度都是偶数（起点 S 和终点 T 可以为任意结点）。

【算法代码：dfs】

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

const int N=105;
int g[N][N];
int du[N],path[N];
int n,m;
int tot;

void dfs(int i) {
    for(int j=1; j<=n; j++) {
        if(g[i][j]==1) {
            g[i][j]=g[j][i]=0;
            dfs(j);
        }
    }
    path[++tot]=i;
}

int main() {
    memset(g,0,sizeof g);
    memset(du,0,sizeof du);
    cin>>n>>m;
    while(m--) {
        int x,y;
        cin>>x>>y;
        g[x][y]=g[y][x]=1;
        du[x]++,du[y]++;
    }

    //Start from odd point with max id
    vector<int> odd;
    for(int i=1; i<=n; i++) {
        if(du[i]%2==1) odd.push_back(i);
    }

    int start=1;
    if(!odd.empty()) {
        sort(odd.begin(),odd.end());
        start=odd.back(); //odd point with max id
    }

    tot=0;
    dfs(start);

    for(int i=1; i<=tot; i++) {
        cout<<path[i]<<" ";
    }

    return 0;
}

/*
in:
5 5
1 2
2 3
3 4
4 5
5 1

out:
1 5 4 3 2 1
*/

【算法代码：bfs】

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

const int N=105;
vector<int> g[N];
vector<int> path;
int du[N];
bool st[N][N];
stack<int> stk;
int n,m;

void bfs(int start) { //hierholzer
    stk.push(start);
    while(!stk.empty()) {
        int t=stk.top();
        bool flag=false;
        for(int i=0; i<g[t].size(); i++) {
            int j=g[t][i];
            if(!st[t][j]) {
                st[t][j]=st[j][t]=true;
                stk.push(j);
                flag=true;
                break;
            }
        }

        if(!flag) {
            stk.pop();
            path.push_back(t);
        }
    }
}

int main() {
    memset(st,false,sizeof st);
    cin>>n>>m;
    while(m--) {
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
        du[a]++,du[b]++;
    }

    for(int i=1; i<=n; i++) {
        sort(g[i].begin(),g[i].end());
    }

    //Start from odd point with max id
    vector<int> odd;
    for(int i=1; i<=n; i++) {
        if(du[i]%2==1) odd.push_back(i);
    }

    int start=1;
    if(!odd.empty()) {
        sort(odd.begin(),odd.end());
        start=odd.back(); //odd point with max id
    }

    bfs(start);

    for(int i=0; i<path.size(); i++) {
        cout<<path[i]<<" ";
    }

    return 0;
}

/*
in:
5 5
1 2
2 3
3 4
4 5
5 1

out:
1 5 4 3 2 1
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/140747624
https://blog.51cto.com/u_14932227/6041733

 

​