首页 > 代码库 > POJ 1041 John's trip 无向图的【欧拉回路】路径输出

POJ 1041 John's trip 无向图的【欧拉回路】路径输出

2024-07-15 18:50:06   222人阅读

欧拉回路第一题TVT

本题的一个小技巧在于：

【建立一个存放点与边关系的邻接矩阵】

1.先判断是否存在欧拉路径

无向图：

欧拉回路：连通 + 所有定点的度为偶数

欧拉路径：连通 + 除源点和终点外都为偶数

 

有向图： 

欧拉回路：连通 + 所有点的入度 == 出度

欧拉路径：连通 + 源点 出度-入度=1 && 终点 入度 - 出度 = 1 && 其余点 入度 == 出度；

 

2.求欧拉路径 ：

step 1：选取起点（如果是点的度数全为偶数任意点为S如果有两个点的度数位奇数取一个奇数度点为S）

step 2：对当前选中的点的所有边扩展，扩展条件（这条边为被标记），若可扩展 ->step 2；否则 step 3；

step 3：将次边计入path结果保存。

 

思路还是很清晰的。

贴代码了：

 1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #include <math.h> 5 #include <iostream> 6 #include <stack> 7 #include <queue> 8 #include <algorithm> 9 10 #define ll long long11 using namespace std;12 const int INF = 0x3f3f3f3f;13 const int MAXN = 8000;14 int vis[2000], indegree[50], map[50][2000], n;15 stack <int> s;16 17 void init(){18     n = 0;19     memset(vis, 0, sizeof(vis));20     memset(map, 0, sizeof(map));//define the relationship between vertex and edge21     memset(indegree, 0, sizeof(indegree));22 }23 24 int euler(int u){25     int i;26     for(i = 1; i <= n; ++i){// n represents edges27         if(map[u][i] && !vis[i]){28             vis[i] = 1;29             euler(map[u][i]);30             s.push(i);31         }32     }33     return 0;34 }35 36 int main(){37     int first, i, j, x, y, w;38     while(cin >> x >> y){39         if(x == 0 && y == 0)    break;40         cin >> w;41         init();42         map[x][w] = y;43         map[y][w] = x;44         ++indegree[x];45         ++indegree[y];46         first = x > y ? y : x;//get first vertex , but speacil judge as u casual47         n = n > w ? n : w;//get numbered largest edge48         while(true){49             cin >> x >> y;50             if(!x && !y)51                 break;52             cin >> w;53             map[x][w] = y;54             map[y][w] = x;55             ++indegree[x];56             ++indegree[y];57             n = n > w ? n : w;58         }59         for(i = 1; i < 45; ++i)//judge if exists solution60             if(indegree[i] % 2) break;61         if(i < 45)62             cout << "Round trip does not exist.\n";63         else{64             euler(first);65             while(!s.empty()){66                 cout << s.top() << ‘ ‘;67                 s.pop();68             }69             cout << endl;70         }71     }72     return 0;73 }

 


联系
我们