【題目描述】

如果一個圖存在一筆畫，則一筆畫的路徑叫做歐拉路，如果最后又回到起點(diǎn)，那這個路徑叫做歐拉回路。

根據(jù)一筆畫的兩個定理，如果尋找歐拉回路，對任意一個點(diǎn)執(zhí)行深度優(yōu)先遍歷；找歐拉路，則對一個奇點(diǎn)執(zhí)行dfs，時間復(fù)雜度為O(m+n)，m為邊數(shù)，n是點(diǎn)數(shù)。

【輸入】

第一行n，m，有n個點(diǎn)，m條邊，以下m行描述每條邊連接的兩點(diǎn)。

【輸出】

歐拉路或歐拉回路，輸出一條路徑即可。

【輸入樣例】

5 5
1 2
2 3
3 4
4 5
5 1

【輸出樣例】

1 5 4 3 2 1

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #include<set> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 501 #define MOD 123 #define E 1e-6 using namespace std; int n,m; int g[N][N]; int dis[N],path[N*2]; int cnt; void dfs(int i) {for(int j=1;j<=n;j++)if(g[i][j]){g[i][j]=0;g[j][i]=0;dfs(j);}path[cnt++]=i; } int main() {cin>>n>>m;for(int i=1;i<=m;i++){int x,y;cin>>x>>y;g[x][y]=1;g[y][x]=1;dis[x]++;dis[y]++;}int start=1;int sum=0;for(int i=1;i<=n;i++)if(dis[i]%2){sum++;if(sum==1)start=i;}dfs(start);for(int i=cnt-1;i>=0;i--)cout<<path[i]<<" ";return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的一笔画问题（信息学奥赛一本通-T1341）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。