柯尼斯堡七橋問題（德語：Königsberger Brückenproblem；英語：Seven Bridges of Königsberg）是圖論中的著名問題。這個問題是基於一個現實生活中的事例：當時東普魯士柯尼斯堡（今日俄羅斯加里寧格勒）市區跨普列戈利亞河兩岸，河中心有兩個小島。小島與河的兩岸有七座橋連接。在所有橋都只能走一遍的前提下，是否能把這個地方所有的橋都走遍？
萊昂哈德·歐拉在1736年在論文《柯尼斯堡的七橋》中，把實際的抽象問題簡化為平面上的點與線組合，每一座橋視為一條線，在圖論中稱為「邊」(edge)，橋所連接的地區視為點，在圖論中稱為「頂點」(vertex, 複數形 vertices)。
→
→
歐拉把問題的實質歸於一筆畫問題，即判斷一個圖是否能夠遍歷完所有的邊而沒有重複，而柯尼斯堡七橋問題則是一筆畫問題的一個具體情境。如果一個圖能一筆畫成，那麼對每一個頂點，路徑中「進入」這個點的邊數等於「離開」這個點的邊數，這時連接這個頂點的邊的總數量必為偶數，這頂點稱為「偶頂點」。這種情況只有起點和終點可以例外，它們可以有奇數個邊，也就是「奇頂點」。從起點離開的邊可以比進入的邊多 1 個，而進入終點的邊也可以比離開的邊多 1 個。
歐拉最後給出任意一種河──橋圖能否全部走一次的判定法則，從而解決了「一筆畫問題」。對於一個給定的連通圖，如果存在超過兩個的奇頂點，那麼滿足要求的路線便不存在了。由於柯尼斯堡七橋問題中存在4個奇頂點，它無法實現符合題意的遍歷。
這七座橋之中，有兩座已經在二戰時的大轟炸中被損毀，現在只剩下五座，令奇頂點只剩下兩個，所以可以一次走完五座橋。
不少數學家都嘗試去解析這類事例。而這些解析，最後發展成為了數學中的圖論。
輸入的第一行含有兩個整數 𝑛, 𝑚 (2 ≤ 𝑛 ≤ 104, 1 ≤ 𝑚 ≤ 105)，代表這個城市被河流切割成了 𝑛 個地區，並有 𝑚 座橋各自連接兩個地區。接下來的 𝑚 行每行有兩個整數 𝑎, 𝑏 (1 ≤ 𝑎, 𝑏 ≤ 𝑛)，代表連接 𝑎, 𝑏 兩地區的一座橋。保證任意兩個地區都存在至少一個路徑可以連通。
在所有橋都只能走一遍的前提下，如果可以把這個城市所有的橋都走遍，請輸出「YES」，否則請輸出「NO」。
4 7 1 2 1 2 1 3 2 3 2 4 2 4 3 4
NO
4 5 1 2 1 3 2 3 2 4 3 4
YES
公開 測資點#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
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 40970 |
|
o067 | 118 | 2024-06-22 01:01 | |
| 40825 |
|
o067 | 118 | 2024-06-14 18:53 | |
| 40817 |
|
o067 | 104 | 2024-06-14 09:09 | |
| 40797 |
|
o067 | 152 | 2024-06-13 18:22 | |
| 40796 |
|
o067 | 111 | 2024-06-13 18:20 |