收獲：

?

代碼：

//哥尼斯堡七橋問題 #include<iostream> using namespace std; #define MAX 1005 int degree[MAX]; int pre[MAX]; void init(int n) {for(int i=1;i<=n;i++){degree[i]=0;pre[i]=i;} } int find(int x) {if(x!=pre[x])return pre[x]=find(pre[x]);return x; } void merge(int a,int b) {int x=find(a);int y=find(b);if(x!=y)pre[x]=y; } int main() {int n,m;cin>>n>>m;init(n);for(int i=0;i<m;i++){int a,b;cin>>a>>b;degree[a]++;degree[b]++;merge(a,b);}int cnt=0;for(int i=1;i<=n;i++){if(pre[i]==i)cnt++;}if(cnt>1){cout<<"0"<<endl;return 0;}for(int i=1;i<=n;i++){if(degree[i]%2!=0){cout<<"0"<<endl;return 0;}}cout<<1<<endl;return 0; }

題目：

哥尼斯堡是位于普累格河上的一座城市，它包含兩個(gè)島嶼及連接它們的七座橋，如下圖所示。

可否走過這樣的七座橋，而且每橋只走過一次？瑞士數(shù)學(xué)家歐拉(Leonhard Euler，1707—1783)最終解決了這個(gè)問題，并由此創(chuàng)立了拓?fù)鋵W(xué)。

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

輸入格式:

輸入第一行給出兩個(gè)正整數(shù)，分別是節(jié)點(diǎn)數(shù)N?(1≤N≤1000)和邊數(shù)M；隨后的M行對(duì)應(yīng)M條邊，每行給出一對(duì)正整數(shù)，分別是該條邊直接連通的兩個(gè)節(jié)點(diǎn)的編號(hào)（節(jié)點(diǎn)從1到N編號(hào)）。

輸出格式:

若歐拉回路存在則輸出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

?

總結(jié)

以上是生活随笔為你收集整理的哥尼斯堡的“七桥问题”（欧拉回路）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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