【題目敘述】https://zerojudge.tw/ShowProblem?problemid=a290
【解題想法】實作 adjacency list 存圖, BFS【筆記】
- vector g[ ]：當有一條路徑 a -> b時，在g[a]中加入b。（G[a]紀錄所有從「城市a」可以直接到達的城市。）
- 查詢從「城市a」是否可以通達「城市b」，利用BFS做法。（另外使用陣列vis[ ] 紀錄某個城市是否已經拜訪過。）
- 【圖例】
- g[1] = {1, 4}
- g[2] = {1, 3, 4}
- g[3] = {5}
- g[4] = {2}
- g[5] = {4}
- 問：是否存在路徑由 3 通往 1？
- 3 -> 5 -> 4 -> 2 -> 1
#include <iostream>
#include <map>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
using namespace std;
int main() {
int n;
ios_base::sync_with_stdio(0);
cin.tie(0);
while (cin >> n){
int m, a, b, vis[800] = {};
vector <int> g[n];
queue <int> q;
cin >> m;
for (int i = 0; i < m; i++){
cin >> a >> b;
if (a==b){
continue;
}
a--;
b--;
g[a].push_back(b);
}
cin >> a >> b;
a--;
b--;
q.push(a);
vis[a] = 1;
while (!q.empty()){
int num;
num = q.front();
q.pop();
for (auto i:g[num]){
if (vis[i] != 1){
vis[i] = 1;
q.push(i);
}
}
}
if (vis[b]==1){
cout << "Yes!!!" << endl;
}else{
cout << "No!!!" << endl;
}
}
}
Python 程式碼 (credit: Amy Chou)
提醒：用try-except讀測資，第 2 組測資會 TLE。改用sys.stdin.readline()。
import sys
for i in sys.stdin:
N, M = map(int, i.split())
# 城市編號從 1 開始
G = [list() for i in range(N+1)]
for i in range(M):
a, b = map(int, sys.stdin.readline().split())
G[a].append(b)
a, b = map(int, sys.stdin.readline().split())
q = [a]
ex = [0 for i in range(N+1)]
while (q):
now = q.pop(0)
ex[now] = 1
for nxt in G[now]:
if (ex[nxt] == 0):
ex[nxt] = 1
q.append(nxt)
if (ex[b]):
print("Yes!!!")
else:
print("No!!!")