题目描述】
如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。
根据一笔画的两个定理，如果寻找欧拉回路，对任意一个点执行深度优先遍历；找欧拉路，则对一个奇点执行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【提示】
【数据范围】
对于100%的数据：1 < n < 100,1 < m < 2000。
#include <bits/stdc++.h>
using namespace std;
int g[501][501],n,m,x,y,degree[501];
stack<int> st;
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);
}
}
st.push(i);
}
int main()
{
int start=1;
memset(g,0,sizeof(g));
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
g[x][y]=g[y][x]=1;
degree[x]++;
degree[y]++;
}
for(int i=1;i<=n;i++)// 注意题目如果找不到奇点就要顶点1出发
if(degree[i]%2==1)
{
start=i;
break;
}
dfs(start);
while(!st.empty())
{
cout<<st.top()<<" ";
st.pop();
}
return 0;
}
标签：笔画,degree,int,1341,信奥赛,回路,例题,欧拉,501 From： https://www.cnblogs.com/nanshaquxinaosai/p/18396805