題目鏈接：點(diǎn)擊查看

題目大意：給出一張由n個(gè)點(diǎn)和m條邊組成的無(wú)向圖，要求我們從點(diǎn)1為起點(diǎn)，沿著每條路都走一遍，正向邊反向邊都走恰好一次，最后到點(diǎn)1結(jié)束，題目需要我們輸出路徑

題目分析：歐拉圖模板題目，因?yàn)轭}目中保證了給出的圖一定時(shí)歐拉圖，而歐拉圖的定義是每個(gè)點(diǎn)的度數(shù)都是偶數(shù)，意思就是只要到達(dá)一個(gè)節(jié)點(diǎn)，那么就必定有一條尚未走過(guò)的邊可以離開(kāi)該點(diǎn)，所以我們可以不斷用dfs搜索，并標(biāo)記已經(jīng)走過(guò)的邊，實(shí)時(shí)輸出就好了

當(dāng)然因?yàn)檫f歸層數(shù)過(guò)多，如果怕爆棧的話也可以自己手寫(xiě)棧然后用循環(huán)模擬dfs遞歸的過(guò)程

最后插個(gè)眼，感覺(jué)這個(gè)博客解釋歐拉路和歐拉圖比較生動(dòng)形象，尤其是解釋了為什么要在回溯的時(shí)候輸出答案而不是在開(kāi)頭就記錄答案：https://blog.csdn.net/a_bright_ch/article/details/82954119

代碼：

遞歸實(shí)現(xiàn)：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e4+100;struct Node {int to;bool flag;Node(int TO){to=TO;flag=true;} };vector<Node>node[N];void dfs(int u) {for(int i=0;i<node[u].size();i++){int v=node[u][i].to;if(node[u][i].flag){node[u][i].flag=false;dfs(v);}}printf("%d\n",u); }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);while(m--){int u,v;scanf("%d%d",&u,&v);node[u].push_back(Node(v));node[v].push_back(Node(u));}dfs(1);return 0; }

循環(huán)實(shí)現(xiàn)：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e4+100;const int M=1e5+100;struct Node {int to,next; }edge[M];int head[N],Stack[M],cnt,top;void addedge(int u,int v) {edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++; }void euler(int st) {Stack[++top]=st;while(top){int x=Stack[top],k=head[x];if(k!=-1){Stack[++top]=edge[k].to;head[x]=edge[k].next;}else{top--;printf("%d\n",x);}} }void init() {memset(Stack,0,sizeof(Stack));memset(head,-1,sizeof(head));cnt=top=0; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);init();int n,m;scanf("%d%d",&n,&m);while(m--){int u,v;scanf("%d%d",&u,&v);addedge(u,v);addedge(v,u);}euler(1);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的POJ - 2230 Watchcow(欧拉图)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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