ZeroJudge 解題筆記：o067. 柯尼斯堡七橋問題

作者：王一哲
日期：2025年12月13日


ZeroJudge 題目連結：o067. 柯尼斯堡七橋問題

解題想法

有奇數條邊的節點數量必須小於等於 2 才有解，可以真的存圖再計算有奇數條邊的節點數量，也可以不存圖、只儲存每個節點是否有奇數條邊。不要真的模擬走訪過程。

Python 程式碼

真的存圖，使用時間約為 0.4 s，記憶體約為 12.7 MB，通過測試。

n, m = map(int, input().split())
graph = dict()
for _ in range(m):
    u, v = map(int, input().split())
    if u not in graph: graph[u] = [v]
    else: graph[u].append(v)
    if v not in graph: graph[v] = [u]
    else: graph[v].append(u)
cnt = 0
flag = True
for v in graph.values():
    if len(v)%2 == 1: cnt += 1
    if cnt > 2:
        flag = False
        break
print("YES" if flag else "NO")

只存每個節點是否有奇數條邊，使用時間約為 0.4 s，記憶體約為 3.4 MB，通過測試。

n, m = map(int, input().split())
vertice = [False]*(n+1)
for _ in range(m):
    u, v = map(int, input().split())
    vertice[u] = not vertice[u]
    vertice[v] = not vertice[v]
cnt = sum(vertice)
print("YES" if cnt <= 2 else "NO")

C++ 程式碼

使用時間約為 18 ms，記憶體約為 92 kB，通過測試。

#include <cstdio>

int main() {
    int n, m; scanf("%d %d", &n, &m);
    bool vertice[n+1] = {false};
    for(int i=0; i<m; i++) {
        int u, v; scanf("%d %d", &u, &v);
        vertice[u] = !vertice[u];
        vertice[v] = !vertice[v];
    }
    int cnt = 0;
    for(int i=0; i<n; i++) {
        if (vertice[i]) cnt++;
    }
    if (cnt <= 2) puts("YES");
    else puts("NO");
    return 0;
}