博客

题目描述】

如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。

根据一笔画的两个定理，如果寻找欧拉回路，对任意一个点执行深度优先遍历；找欧拉路，则对一个奇点执行dfs，时间复杂度为O(m+n)，m为边数，n是点数。

【输入】

第一行n，m，有n个点，m条边，以下m行描述每条边连接的两点。

【输出】

欧拉路或欧拉回路,输出一条路径即可。

【输入样例】

5 5

1 2

2 3

3 4

4 5

5 1

【输出样例】

1 5 4 3 2 1

多种打印方法

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f

using namespace std;
const int N=1e4+5;
int du[N],g[N][N];//g存储边信息
int n,m,x,y;
vector<int> res;
stack<int> s;

void dfs(int x)
{
    //s.push(x);
    //printf("%d ",x);
    for(int i=1;i<=n;i++)
    {
        if(g[x][i])
        {
            //printf("%d ",i);
            g[x][i]=g[i][x]=0;
            dfs(i);
            //printf("%d ",i);
        }
    }
    printf("%d ",x);
    //res.push_back(x);
}
int main()
{
    cin >> n >> m;
    while(m--)
    {
        cin >> x >> y;
        du[x]++;
        du[y]++;
        g[x][y]=g[y][x]=1;
    }
    int root,i;
    for(i=1;i<=n;i++)
    {
        if(du[i]%2)
        {
            root=i;
            break;
        }
    }
    if(i<=n)
        dfs(root);
    else
        dfs(1);
    //for(int i=0;i<res.size();i++)
      //  printf("%d ",res[i]);
    /*while(!s.empty())
    {
        printf("%d ",s.top());
        s.pop();
    }*/
    return 0;
}