ZeroJudge 解題筆記：a290. 新手訓練系列 ~ 圖論

作者：王一哲
日期：2025年1月25日



ZeroJudge 題目連結：a290. 新手訓練系列 ~ 圖論

解題想法

先用鄰接串列儲存節點之間的連接方式，注意，這題是有向圖。由於題目要問城市 A 是否能走到城市 B，用 BFS 從 A 開始測試，如果能夠走到 B，就可以跳出 BFS 並且印出 Yes!!!，如果跑完 BFS 還是沒有走到 B 就印出 No!!!。

Python 程式碼

這題的測資大到 Python 連用 BFS 都過不了。

import sys
from collections import deque

for line in sys.stdin:
    N, M = map(int, line.split())  # N 個城市，M 條道路
    adj = [[] for _ in range(N+1)]  # 有向圖
    for _ in range(M):  # 讀取 M 行資料
        a, b = map(int, input().split())  # 城市 a、b
        adj[a].append(b)  # a 可以走到 b
    A, B = map(int, input().split())  # 起點A、終點 B
    que = deque([A])  # 待走訪佇列，先放入 A
    flag = False  # 是否能走到終點，假設為 False
    while que:  # 如果 que 還有資料繼續執行
        u = que.popleft()  # 從 que 最前面讀取並移除資料
        if u == B:  # 可以走到終點
            flag = True  # flag 設定為 True
            break  # 中止 while 迴圈
        for v in adj[u]: que.append(v)  # 將 u 可以走到的點都加入 que
    print("Yes!!!" if flag else "No!!!")  # 印出答案

C++ 程式碼

使用時間約為 0.2 s，記憶體約為 6.4 MB，通過測試。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N, M;
    while(cin >> N >> M) {  // N 個城市，M 條道路
        vector<vector<int>> adj (N+1);  // 有向圖
        for(int i=0; i<M; i++) {  // 讀取 M 行資料
            int a, b; cin >> a >> b;  // 城市 a、b
            adj[a].push_back(b);  // a 可以走到 b
        }
        int A, B; cin >> A >> B;  // 起點A、終點 B
        queue<int> que; que.push(A);  // 待走訪佇列，先放入 A
        bool flag = false;  // 是否能走到終點，假設為 false
        while(!que.empty()) {  // 如果 que 還有資料繼續執行
            int u = que.front(); que.pop();  // 從 que 最前面讀取並移除資料
            if (u == B) {  // 可以走到終點
                flag = true;  // flag 設定為 true
                break;  // 中止 while 迴圈
            }
            for(int v : adj[u]) que.push(v);  // 將 u 可以走到的點都加入 que
        }
        cout << (flag ? "Yes!!!\n" : "No!!!\n");  // 印出答案
    }
    return 0;
}