alan23273850 的刷題筆記
d279: 00280 - Vertex
Tags: graph
出處：https://zerojudge.tw/ShowProblem?problemid=d279
提交：https://zerojudge.tw/Submissions?problemid=d279&account=allllllan123456
問題：給定一張 $n\in[1,100]$ 個點的有向圖，定義頂點 p 可以到達頂點 r，如果從 p 到 r 至少有一條路徑包含至少一條邊。現在給定一些起點，要找這些起點分別無法獨自到達的頂點群。
解法：這題的模型其實跟 b298 超級像，直接把 code 拿來改即可！唯一的差別在於，b298 的 DFS 起點要算成已走訪，這題的起點不能算成已走訪，在寫遞迴函式的時候注意一下即可。
1#include <bits/stdc++.h>
2using namespace std;
3
4bool visit[101];
5vector<int> adj[101];
6
7void dfs(int v) {
8 for (auto u: adj[v])
9 if (!visit[u])
10 visit[u] = true, dfs(u);
11}
12
13int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
14 int n;
15 while (cin >> n && n) { int i, j;
16 for (int i=1; i<=n; i++) adj[i].clear();
17 while (cin >> i && i)
18 while (cin >> j && j)
19 adj[i].push_back(j);
20 int m; cin >> m;
21 while (m--) { memset(visit, false, sizeof visit);
22 cin >> i; dfs(i);
23 cout << accumulate(visit+1, visit+n+1, 0, [](const auto& a, const auto& b){ return a + !b; });
24 for (int i=1; i<=n; i++)
25 if (!visit[i])
26 cout << ' ' << i;
27 cout << '\n';
28 }
29 }
30 return 0;
31}