題意：

　　Bessie 最近做了農(nóng)場看守，他每天晚上的工作就是巡視農(nóng)場并且保證沒有壞人破壞農(nóng)場。從谷倉出發(fā)去巡視，并且最終回到谷倉。

　　Bessie 視力不是很好，不能像其他農(nóng)場的看守一樣，對農(nóng)場的每一條連接不同場地的路走一遍就可以發(fā)現(xiàn)是不是有異常情況，他需要每條路都走兩遍，并且這兩邊必須是不同的方向，因為他覺得自己應該不會兩次都忽略農(nóng)場中的異常情況。

　　每塊地之間一定會由至少一條路相連。現(xiàn)在的任務就是幫他制定巡視路線。前提假設(shè)一定存在滿足題意的路徑。

輸入：

　　第一行輸入兩個數(shù)N(2 <= N <= 10000)和M(1 <= M <= 50000)，表示農(nóng)場一共有N塊地M條路。

　　第二到M+1行輸入兩個整數(shù)，表示對應的兩塊地之間有一條路。

輸出：

　　輸出我2 * (m + 1)行，每行一個數(shù)字，表示Bessie 的巡查路徑上地的編號，1號為谷倉，從1開始，從1結(jié)束。如果有多種你答案，輸出任意一種。

樣例輸入

4 5

1 2

1 4

2 3

2 4

3 4

樣例輸出

1

2

3

4

2

1

4

3

2

4

1

解題思路：

　　由于是無向邊，而且每條邊要求正反各走一次，所以一定存在歐拉回路。存圖時把每條無向邊看成兩條相反的有向邊，直接利用歐拉回路求解。
　（轉(zhuǎn)自：http://www.cnblogs.com/Ash-ly/p/5398425.html）
　
不用回溯 一定有解

#include <cstdio> using namespace std; int n,m,tot=2,v[100001],first[10001],next[100001],vis[1000001],a[1000001],xxx,yyy; void add(int xx,int yy){v[tot]=yy,next[tot]=first[xx],first[xx]=tot++;} void dfs(int x){for(int i=first[x];i;i=next[i])if(!vis[i]) vis[i]=1,dfs(v[i]),printf("%d\n",x); } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)scanf("%d%d",&xxx,&yyy),add(xxx,yyy),add(yyy,xxx);printf("1\n");dfs(1); }

轉(zhuǎn)載于:https://www.cnblogs.com/SiriusRen/p/6532459.html

總結(jié)

以上是生活随笔為你收集整理的POJ 2230 DFS的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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