題目來(lái)源：PTA 數(shù)據(jù)結(jié)構(gòu)與算法題目集（中文）

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

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

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

輸入格式:

輸入第一行給出兩個(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

思路：

1. 無(wú)向圖是歐拉圖（存在歐拉回路）當(dāng)且僅當(dāng)該圖是連通的且沒(méi)有奇度頂點(diǎn)；無(wú)向圖是半歐拉圖（存在歐拉通路）當(dāng)且僅當(dāng)該圖是連通的且恰有兩個(gè)奇度頂點(diǎn)；

??? 有向圖是歐拉圖（存在歐拉回路）當(dāng)且僅當(dāng)該圖是強(qiáng)連通的且每個(gè)頂點(diǎn)入度等于出度；有向圖是半歐拉圖（存在歐拉通路）當(dāng)且僅當(dāng)該圖是單向連通的且恰有兩個(gè)奇度頂點(diǎn)；

2. 本題中首先需要判斷該圖是否連通圖，若是連通圖則再判斷是否有無(wú)奇度頂點(diǎn)；

3. 使用并查集來(lái)判斷該圖是否為連通圖，設(shè)置一個(gè)數(shù)組ab，每個(gè)元素初始化為對(duì)應(yīng)下標(biāo)（每個(gè)元素的根結(jié)點(diǎn)為自己），每輸入一條邊，便在數(shù)組ab中尋找邊的頂點(diǎn)a和b（a<b）的根結(jié)點(diǎn)fa和fb，若fa和fb不相等（沒(méi)有在一個(gè)連通分支里），則把fb指向fa（fa作fb的根結(jié)點(diǎn)）；

4. 使用一個(gè)數(shù)組v，每個(gè)元素初始化0，每輸入一條邊，便在數(shù)組v中增加對(duì)應(yīng)頂點(diǎn)a和b和度數(shù)；

5. 找出每個(gè)頂點(diǎn)在并查集數(shù)組ab中的根結(jié)點(diǎn)，并判斷是否都相等，相等則為連通圖；

6. 根據(jù)數(shù)組v判斷每個(gè)頂點(diǎn)的度數(shù)是否為偶數(shù)；全為偶數(shù)則是歐拉圖（前提是5成立）；

?

//7-32 哥尼斯堡的“七橋問(wèn)題” #include <iostream> using namespace std; #include <algorithm> #include <vector> #include <set> #define N 1005int ab[N],n; //ab為并查集數(shù)組int find(int x) //尋找x的根結(jié)點(diǎn) {if(x==ab[x]) return x;return ab[x]=find(ab[x]);}bool liantong() //判斷是否為連通圖 {set <int> se;for(int i=1;i<=n&&se.size()<=1;i++)se.insert(find(i));if(se.size()==1)return true;return false;}bool degreeOK(vector<int> v) //判斷連通無(wú)向圖是否為歐拉圖 {for(int i=1;i<=n;i++)if(v[i]%2!=0)return false;return true;} int main() {int m,i,a,b;cin>>n>>m;vector<int> v(n+1,0); //統(tǒng)計(jì)度數(shù)for(i=1;i<=n;i++) //初始化并查集數(shù)組ab[i]=i;for(i=0;i<m;i++){cin>>a>>b;if(a>b)swap(a,b); //避免互相指向（循環(huán)指向）產(chǎn)生多個(gè)根節(jié)點(diǎn)，對(duì)所有節(jié)點(diǎn)都是大的指向小的v[a]++;v[b]++;int fa=ab[a]; //找出a的跟節(jié)點(diǎn)faint fb=ab[b]; //找出b的跟節(jié)點(diǎn)fbif(fa!=fb)ab[fb]=fa; //合并，fb指向fa,大的指向小的}if(liantong()&&degreeOK(v)) //連通且無(wú)奇度頂點(diǎn)cout<<1<<endl;elsecout<<0<<endl;return 0; }

?

?

?

?

總結(jié)

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

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