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

俗話說：「條條大路通羅馬」

範例測資

範例輸入範例輸出
EOF 輸入，每筆輸入有兩個正整數 N 和 M (N <= 800，M <= 10000)
代表有 N 個城市 M 條道路！
請注意，道路是有方向性的！
接下來有 M 行， 每行有 2 個正整數 a 和 b (1 <= a，b <= N)
代表 a 城市 可以到 b 城市
最後一行有兩個正整數 A 和 B (1 <= A，B <= N)		如果 A 城市 可以到達 B 城市，
請輸出「Yes!!!」
不行請輸出「No!!!」
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		Yes!!!
ZeroJudge A290 範例測資

解題思路

使用 Map<int, vector<int>> 來存取哪些城市可以通往哪些城市，並且用 BFS 的方式尋找哪些城市可以通往哪些城市，每次進到 BFS 的時候需要判斷哪些城市已經被 Push_Back 到下一次的起點了，如果已經被 Push_Back 過的起點就不再 Push_Back。

如果走到終點城市就可以輸出 Yes，如果遇到起點的陣列長度為 0 就代表永遠走不到輸出No。

範例程式碼－ZeroJudge A290: 新手訓練系列 ~ 圖論

#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);
    }
}

//ZeroJudge A290
//Dr. SeanXD
標籤

相關文章

發佈留言