alan23273850 的刷題筆記
a280: 小朋友上樓梯
Tags: graph
出處：https://zerojudge.tw/ShowProblem?problemid=a280
提交：https://zerojudge.tw/Submissions?problemid=a280&account=allllllan123456
問題：給定一張有編號 0 到 100 共 101 個點、$k\in[1,10000]$ 條有向邊的圖，請問從指定點 0 可否到達指定點 $n\in[1,100]$？
解法：就單純 DFS，並且倚賴函式回傳值說明子樹有沒有包含 n，最後得到的答案就是我們要的。另外為了避免環的出現導致重複走訪，須多用一個陣列 visit 記錄頂點是否已經看過，已經看過的點就不要再繼續走下去了。
1#include <bits/stdc++.h>
2using namespace std;
3
4int n;
5bool visit[101];
6vector<int> adj[101];
7
8bool dfs(int v) {
9 if (v == n) 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 a, b, k;
19 while (cin >> n >> k) {
20 memset(visit, false, sizeof visit);
21 for (int i=0; i<=100; i++) adj[i].clear();
22 while (k--) cin >> a >> b, adj[a].push_back(b);
23 cout << (dfs(0) ? "Ok!\n" : "Impossib1e!\n");
24 }
25 return 0;
26}