alan23273850 的刷題筆記
b298: 老闆阿我要退貨
Tags: graph
出處：https://zerojudge.tw/ShowProblem?problemid=b298
提交：https://zerojudge.tw/Submissions?problemid=b298&account=allllllan123456
問題：給定 $N\in[1,10000]$ 個廠商、$M\in[1,100000]$ 條表上下游關係的有向邊，以及 $L\in[1,10000]$ 個廠商出問題，只要上游廠商有問題，下游廠商也會跟著有問題，那麼接下來是 $Q\in[1,10000]$ 筆詢問指定的廠商是否有問題。
解法：很簡單，就是對每個出問題的廠商都作一次 DFS，而且只要每個走過的地方都標示為「有問題」，下次再遇到同樣已經標示的地方就停止走訪，會省下很多時間，也可以避免掉圖內的環可能會造成停不下來的問題。(說不定這題根本就沒有環？)
1#include <bits/stdc++.h>
2using namespace std;
3
4bool prob[10001];
5vector<int> adj[10001];
6
7void dfs(int v) {
8 if (prob[v]) return;
9 prob[v] = true;
10 for (auto u: adj[v]) dfs(u);
11}
12
13int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
14 int a, b, N, M, L, Q; cin >> N >> M >> L >> Q;
15 while (M--) cin >> a >> b, adj[a].push_back(b);
16 while (L--) cin >> a, dfs(a);
17 while (Q--) cin >> a, cout << (prob[a] ? "TUIHUOOOOOO\n" : "YA~~\n");
18 return 0;
19}