ZeroJudge A290: 新手訓練系列 ~ 圖論

題目敘述

本題採用EOF方式收資料，每筆資料第一行有兩個正整數N和M，借下來會有M行，每行有兩個正整數a和b，代表城市a可以走到城市b，但是只能單向通過不能雙向，最後會有兩個正整數c和d。要求輸出是否能從城市c走到城市d。

範例輸入 #1

8 32

7 4

2 5

7 5

3 7

2 1

2 2

2 4

4 4

4 7

8 5

7 5

5 2

6 7

7 5

8 8

4 7

6 3

4 1

4 4

8 7

3 4

2 6

6 1

6 8

4 5

7 5

6 6

4 4

2 6

5 3

7 4

1 3

1 3

範例輸出 #1

Yes!!!

解題思路

使用Map<int, vector<int>>來存取哪些城市可以通往哪些城市，並且用BFS的方式尋找哪些城市可以通往哪些城市，如果走到終點城市就可以輸出Yes。

解題程式碼如下 (僅供參考)：

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

map<int, vector<int>>MAP;
int N, M, start, finish;

void BFS(vector<int>start)
{
    if (start.size() == 0)
    {
        cout << "No!!!\n";
        return;
    }
    vector<int>newStart;
    map<int, int>appear;
    for (int i = 0; i<start.size(); i++)
    {
        vector<int>step = MAP[start[i]];
        for (int j = 0; j<step.size(); j++)
        {
            if (step[j] == finish)
            {
                cout << "Yes!!!\n";
                return;
            }
            if (appear[step[j]] == 0)
            {
                appear[step[j]]++;
                newStart.push_back(step[j]);
            }
        }
    }
    BFS(newStart);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    while (cin >> N >> M)
    {
        MAP.clear();
        for (int i = 0; i<M; i++)
        {
            int a, b;
            cin >> a >> b;
            MAP[a].push_back(b);
        }
        cin >> start >> finish;
        vector<int>v;
        v.push_back(start);
        BFS(v);
    }
}