alan23273850 的刷題筆記
a290: 新手訓練系列 ~ 圖論
Tags: graph
出處：https://zerojudge.tw/ShowProblem?problemid=a290
提交：https://zerojudge.tw/Submissions?problemid=a290&account=allllllan123456
問題：給定一張至多 800 個點、$M\in[1,10000]$ 條有向邊的圖，請問從指定點 A 可否到達指定點 B？
解法：就單純 DFS，並且倚賴函式回傳值說明子樹有沒有包含 B，最後得到的答案就是我們要的。另外為了避免環的出現導致重複走訪，須多用一個陣列 visit 記錄頂點是否已經看過，已經看過的點就不要再繼續走下去了。
1#include <bits/stdc++.h>
2using namespace std;
3
4int M;
5bool visit[801];
6vector<int> adj[801];
7
8bool dfs(int v) {
9 if (v == M) return true;
10 if (visit[v]) return false;
11 bool result = false;
12 visit[v] = true;
13 for (auto u: adj[v]) result |= dfs(u);
14 return result;
15}
16
17int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
18 int N, a, b;
19 while (cin >> N >> M) {
20 memset(visit, false, sizeof visit);
21 while (N--) adj[N+1].clear();
22 while (M--) cin >> a >> b, adj[a].push_back(b);
23 cin >> N >> M;
24 cout << (dfs(N) ? "Yes!!!\n" : "No!!!\n");
25 }
26 return 0;
27}