#53619: 影片講解 並非最速解但一般使用足以
tryit163281@gmail.com
(CodingBarJoe(被逼著不得不刷題=_=))
學校
:
不指定學校
編號 : 74499
來源 : [210.68.224.131]
最後登入時間 ：
2025-09-30 15:45:58
//判讀題目
//建立有向圖(vector、unordered_map)，找出是否有辦法從起點跑到終點(BFS)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 805; //題目說 N <= 800
vector<int> adj[MAXN]; //建立有向圖用，也可以用我之前說過的unordered_map
int visited[MAXN]; //是否拜訪過
int bfs(int start, int end, int n) {
if (start == end) {
return 1;
}
// 實際會使用到的 visited 陣列
for (int i = 1; i <= n; ++i) {
visited[i] = 0;
}
queue<int> q;
q.push(start);
visited[start] = 1;
// BFS迴圈
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (v == end) {
return 1; // 找到目標，立即返回
}
if (visited[v] == 0) {
visited[v] = 1;
q.push(v);
}
}
}
return 0;//跑完了都找不到終點
}
int main() {
//降低I/O所花時間，可加可不加
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
while (cin >> n >> m) {
// 清理實際使用的節點
for (int i = 1; i <= n; ++i) {
adj[i].clear();
}
// 建立有向圖
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
}
int start_node, end_node;
cin >> start_node >> end_node;
// 使用 BFS 搜尋
if (bfs(start_node, end_node, n)) {
cout << "Yes!!!\n";
} else {
cout << "No!!!\n";
}
}
return 0;
}