o067. 柯尼斯堡七橋問題
Tags :
Accepted rate : 52人/57人 ( 91% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-06-14 19:49

Content

柯尼斯堡七橋問題(德語:Königsberger Brückenproblem;英語:Seven Bridges of Königsberg)是圖論中的著名問題。這個問題是基於一個現實生活中的事例:當時東普魯士柯尼斯堡(今日俄羅斯加里寧格勒)市區跨普列戈利亞河兩岸,河中心有兩個小島。小島與河的兩岸有七座橋連接。在所有橋都只能走一遍的前提下,是否能把這個地方所有的橋都走遍?

萊昂哈德·歐拉在1736年在論文《柯尼斯堡的七橋》中,把實際的抽象問題簡化為平面上的點與線組合,每一座橋視為一條線,在圖論中稱為「邊」(edge),橋所連接的地區視為點,在圖論中稱為「頂點」(vertex, 複數形 vertices)。

歐拉把問題的實質歸於一筆畫問題,即判斷一個圖是否能夠遍歷完所有的邊而沒有重複,而柯尼斯堡七橋問題則是一筆畫問題的一個具體情境。如果一個圖能一筆畫成,那麼對每一個頂點,路徑中「進入」這個點的邊數等於「離開」這個點的邊數,這時連接這個頂點的邊的總數量必為偶數,這頂點稱為「偶頂點」。這種情況只有起點和終點可以例外,它們可以有奇數個邊,也就是「奇頂點」。從起點離開的邊可以比進入的邊多 1 個,而進入終點的邊也可以比離開的邊多 1 個。

歐拉最後給出任意一種河──橋圖能否全部走一次的判定法則,從而解決了「一筆畫問題」。對於一個給定的連通圖,如果存在超過兩個的奇頂點,那麼滿足要求的路線便不存在了。由於柯尼斯堡七橋問題中存在4個奇頂點,它無法實現符合題意的遍歷。

這七座橋之中,有兩座已經在二戰時的大轟炸中被損毀,現在只剩下五座,令奇頂點只剩下兩個,所以可以一次走完五座橋。

不少數學家都嘗試去解析這類事例。而這些解析,最後發展成為了數學中的圖論

Input

輸入的第一行含有兩個整數 𝑛, 𝑚 (2 ≤ 𝑛 ≤ 104, 1 ≤ 𝑚 ≤ 105),代表這個城市被河流切割成了 𝑛 個地區,並有 𝑚 座橋各自連接兩個地區。接下來的 𝑚 行每行有兩個整數 𝑎, 𝑏 (1 ≤ 𝑎, 𝑏 ≤ 𝑛),代表連接 𝑎, 𝑏 兩地區的一座橋。保證任意兩個地區都存在至少一個路徑可以連通。

Output

在所有橋都只能走一遍的前提下,如果可以把這個城市所有的橋都走遍,請輸出「YES」,否則請輸出「NO」。

Sample Input #1
4 7
1 2
1 2
1 3
2 3
2 4
2 4
3 4
Sample Output #1
NO
Sample Input #2
4 5
1 2
1 3
2 3
2 4
3 4
Sample Output #2
YES
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <1M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <1M
公開 測資點#9 (10%): 1.0s , <1M
Hint :
Tags:
出處:
Wikipedia板橋高中教學題 [管理者: snail (蝸牛) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
40970 seancai78@gm ... (風月春秋) o067
45 2024-06-22 01:01
40825 hs210023@stu ... (天底下最帥的那個男人) o067
解答 python
61 2024-06-14 18:53
40817 s10900156@nh ... (ShanC) o067
解題思路
58 2024-06-14 09:09
40797 n0970616056@ ... (CIOU-HE-CHEN) o067
74 2024-06-13 18:22
40796 n0970616056@ ... (CIOU-HE-CHEN) o067
解答 python
60 2024-06-13 18:20