立志用最少的代碼做最高效的表達(dá)

---

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

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

這個(gè)問(wèn)題如今可以描述為判斷歐拉回路是否存在的問(wèn)題。歐拉回路是指不令筆離開(kāi)紙面，可畫(huà)過(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

---

歐拉回路模板題。

歐拉回路要滿(mǎn)足兩個(gè)條件：
1、所有節(jié)點(diǎn)連通
2、滿(mǎn)足1的條件下，所有節(jié)點(diǎn)的度數(shù)為偶數(shù)（入度數(shù)+出度數(shù)）

判斷方法：
判斷條件一：并查集orDFS（并查集效率更高）
判斷條件二：定義一個(gè)度數(shù)數(shù)組，存儲(chǔ)度數(shù)并判斷即可。

---

#include<iostream> #include<cstdio> using namespace std;const int maxn = 1010; int degree[maxn]; //每個(gè)節(jié)點(diǎn)的度數(shù) int pre[maxn]; //并查集int find_(int x) {return x==pre[x] ? x : pre[x]=find_(pre[x]); } void merge(int x, int y) {int fx = find_(x);int fy = find_(y);if(fx > fy) pre[fx] = fy;else pre[fy] = fx; }int main() {ios::sync_with_stdio(false);for(int i = 1; i < maxn; i++) pre[i] = i; //初始化int n, k; cin >> n >> k;for(int i = 0 ; i < k; i++) {int x1, x2; cin >> x1 >> x2;merge(x1, x2);degree[x1]++; degree[x2]++;} bool flag = true;//結(jié)果判斷：判斷是否連通、判斷度數(shù)是否為偶數(shù) int num = 0; //連通塊個(gè)數(shù) for(int i = 1; i <= n; i++) {//度數(shù)為奇數(shù)不連通 if(degree[i]%2!=0) flag = false;//連通塊個(gè)數(shù)>1不連通 if(i == pre[i]) num++;}if(num != 1) flag = false;cout << (flag ? "1\n" : "0\n");return 0; }

---

耗時(shí)：

---

??????——弱小和無(wú)知不是生存的障礙，傲慢才是。

總結(jié)

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

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