【解題】Zerojudge a290: 新手訓練系列 ~ 圖論

題目連結

a290: 新手訓練系列 ~ 圖論

我的想法

先將圖建好，再用 BFS 慢慢走訪，從訪問的起點開始，走過的地方都標記為 true ，若最後終點是 true，輸出 Yes!!!，否則 No!!!

參考解答

a290

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N, M;
    while (cin >> N >> M) {
        vector<int> d[N];
        queue<int> q;
        bool check[800] = {false};
        for (int i = 0; i < M; i++) {
            int a, b;
            cin >> a >> b;
            a--;
            b--;
            d[a].push_back(b);
        }
        // 將能走的路徑都設為 true
        int A, B;
        cin >> A >> B;
        A--;
        B--;
        q.push(A);
        check[A] = true;
        while (!q.empty()) {
            int temp = q.front();
            q.pop();
            for (auto &i : d[temp]) {
                if (!check[i]) {
                    check[i] = true;
                    q.push(i);
                }
            }
        }
        // 訪問 B 點是否能走到
        if (check[B]) {
            cout << "Yes!!!\n";
        } else {
            cout << "No!!!\n";
        }
    }
    return 0;
}