forked from drken1215/book_algorithm_solution
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcode_13_4.cpp
More file actions
38 lines (32 loc) · 848 Bytes
/
code_13_4.cpp
File metadata and controls
38 lines (32 loc) · 848 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <vector>
using namespace std;
using Graph = vector<vector<int>>;
// 深さ優先探索
vector<bool> seen;
void dfs(const Graph &G, int v) {
seen[v] = true; // v を訪問済にする
// v から行ける各頂点 next_v について
for (auto next_v : G[v]) {
if (seen[next_v]) continue; // next_v が探索済だったらスルー
dfs(G, next_v); // 再帰的に探索
}
}
int main() {
// 頂点数と辺数、s と t
int N, M, s, t;
cin >> N >> M >> s >> t;
// グラフ入力受取
Graph G(N);
for (int i = 0; i < M; ++i) {
int a, b;
cin >> a >> b;
G[a].push_back(b);
}
// 頂点 s をスタートとした探索
seen.assign(N, false); // 全頂点を「未訪問」に初期化
dfs(G, s);
// t にたどり着けるかどうか
if (seen[t]) cout << "Yes" << endl;
else cout << "No" << endl;
}