7-2 哥尼斯堡的“七橋問題” (25分)
哥尼斯堡是位于普累格河上的一座城市，它包含兩個島嶼及連接它們的七座橋，如下圖所示。

可否走過這樣的七座橋，而且每橋只走過一次？瑞士數學家歐拉(Leonhard Euler，1707—1783)最終解決了這個問題，并由此創立了拓撲學。

這個問題如今可以描述為判斷歐拉回路是否存在的問題。歐拉回路是指不令筆離開紙面，可畫過圖中每條邊僅一次，且可以回到起點的一條回路。現給定一個無向圖，問是否存在歐拉回路？

輸入格式:
輸入第一行給出兩個正整數，分別是節點數N (1≤N≤1000)和邊數M；隨后的M行對應M條邊，每行給出一對正整數，分別是該條邊直接連通的兩個節點的編號（節點從1到N編號）。

輸出格式:
若歐拉回路存在則輸出1，否則輸出0。

輸入樣例1:
6 10
1 2
2 3
3 1
4 5
5 6
6 4
1 4
1 6
3 4
3 6
輸出樣例1:
1
輸入樣例2:
5 8
1 2
1 3
2 3
2 4
2 5
5 3
5 4
3 4
輸出樣例2:
0

AC代碼

#include <iostream> using namespace std; const int MaxSize = 1010; int visited[MaxSize] = {0}; class MGraph { public:MGraph(int n, int e);~MGraph( ) { };void DFTraverse(int v);int edge[MaxSize][MaxSize];int vertexNum, edgeNum; };MGraph:: MGraph(int n, int e) {int i, j, k;vertexNum = n;edgeNum = e;for (i = 0; i < vertexNum; i++)for (j = 0; j < vertexNum; j++)edge[i][j] = 0;for (k = 0; k < edgeNum; k++){scanf("%d%d",&i,&j);edge[i-1][j-1] = 1;edge[j-1][i-1] = 1;} } void MGraph :: DFTraverse(int v) {visited[v] = 1;for (int j = 0; j < vertexNum; j++){if (edge[v][j] == 1 && visited[j] == 0){DFTraverse(j);}} }int main( ) {int i,n,m;cin>>n>>m;MGraph MG{n,m};MG.DFTraverse(0);for (i = 0; i < n; i++){if(visited[i] == 0){cout<<"0"<<endl;return 0;}}int cnt,j;for(i=0;i<n;i++){cnt=0;for(j=0;j<n;j++){cnt+=MG.edge[i][j];}if(cnt%2){cout<<"0"<<endl;return 0;}}cout<<"1"<<endl;return 0; }

領QQ一筆畫紅包領多了QWQ
剛開始想著，頂點度為奇數的個數，0或2個就行
第二個樣例都沒過哈哈哈
百度一下_(:з」∠)_

無向圖存在歐拉回路的充要條件
一個無向圖存在歐拉回路，當且僅當該圖所有頂點度數都為偶數,且該圖是連通圖。
有向圖存在歐拉回路的充要條件
一個有向圖存在歐拉回路，所有頂點的入度等于出度且該圖是連通圖。

• 判斷是否為連通圖
  隨便找一個頂點遍歷一遍（我用的DFS）
  遍歷完了，看一看是不是所有頂點都被遍歷了_(:з」∠)_

總結

以上是生活随笔為你收集整理的7-2 哥尼斯堡的“七桥问题” (25分)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。