tags: APCS

a290－新手訓練系列 ~ 圖論

題目連結： a290

題目解析

這個題目要求我們判斷從城市 A 是否能夠到達城市 B。這可以轉換成圖論中的「尋找從節點 A 到節點 B 是否存在路徑」問題。由於道路是有方向性的，因此我們要考慮有向圖。

解題方向

• 將每個城市視為圖中的一個節點，每條道路則是一條有方向性的邊。
• 我們可以利用 廣度優先搜尋（BFS） 來檢查從節點 A 是否可以到達節點 B。
• 初始化時，我們將 A 作為起點，並標記它已被訪問，接著遍歷與 A 相鄰的所有節點，直到找到節點 B 或遍歷所有可能路徑為止。

程式解析

1. 資料結構：
   • 使用一個列表 G 來儲存每個城市可以到達的鄰接城市。例如，G[u] 代表從城市 u 出發的所有目的地城市的列表。
2. 讀取輸入：
   • 首先讀取 N 和 M，表示城市數量和道路數量。
   • 接著讀取每條道路的起點和終點，並更新 G 以儲存鄰接資訊。
   • 最後讀取要檢查的兩個城市 A 和 B。
3. 廣度優先搜尋（BFS）：
   • 使用 route 列表來存放下一個要訪問的城市，並且使用 visit 列表來標記已經訪問過的城市。
   • 不斷從 route 中取出當前城市，並檢查它可以到達的所有城市，如果這些城市未被訪問過，則將其加入 route。
4. 判斷結果：
   • 如果在搜尋過程中，城市 B 被訪問到，則說明存在從 A 到 B 的路徑，輸出 "Yes!!!"。
   • 否則，輸出 "No!!!"。

完整程式碼

import sys

# 使用 sys.stdin 來讀取多筆輸入資料
for s in sys.stdin:
    N, M = map(int, s.split())

    G = [[] for i in range(N + 1)]  # 鄰接列表
    for i in range(M):
        u, v = map(int, input().split())
        G[u].append(v)  # 將道路加入圖中

    A, B = map(int, input().split())
    route = [A]  # 開始點
    visit = [0 for i in range(N + 1)]  # 訪問標記

    # BFS
    while len(route) > 0:
        now = route.pop(0)
        visit[now] = 1
        for next_city in G[now]:
            if visit[next_city] == 0:
                visit[next_city] = 1
                route.append(next_city)

    if visit[B] == 1:
        print("Yes!!!")
    else:
        print("No!!!")

改用sys.stdin.readline()

import sys

#start
for s in sys.stdin:
    N, M = map(int, s.split())

    G = [ [] for i in range(N+1) ]
    for i in range(M):
        u, v = map(int, sys.stdin.readline().split())
        G[u].append(v)

    A, B = map(int, sys.stdin.readline().split())
    route = [A]
    visit = [ 0 for i in range(N+1) ]

    while len(route)>0:
        now = route.pop(0)
        visit[now] = 1
        for next_city in G[now]:
            if visit[next_city] == 0:
                visit[next_city] = 1
                route.append(next_city)

    if visit[B] == 1:
        print("Yes!!!")
    else:
        print("No!!!")

範例解析

• 輸入範例 #1：
  • 城市 1 到城市 3 有兩條直接道路。
  • 輸出 "Yes!!!" 因為 A 城市可以到達 B 城市。