문제
https://www.acmicpc.net/problem/2152
문제해설
길어서 링크 참조
문제풀이
백준 ATM 문제와 유사한 문제다.
ATM 문제에서 시작과 도착지점을 정해주고 비용 대신 노드의 개수로 바꾸면 풀린다.
참고로 ATM 문제의 풀이는 이 곳에서 볼 수 있다.
ATM 문제 풀이에서 자세히 설명했듯이
SCC를 구해 SCC로 묶인 노드들을 하나의 노드로 처리해서 새로운 그래프를 만든다.
그 후에 BFS를 이용해 시작점과 도착점까지 거친 노드의 개수를 출력해주면 된다.
만약 출발점과 도착점이 하나의 SCC로 묶일 수 있다.
1
2
3
4
if (start == target) {
cout << country[start];
return 0;
}
그 경우에는 위 코드처럼 BFS를 돌기 전에 출력해주었다.
참고로 위 코드에서 country[start]라고 써야하는 것을
country[scc[start]]라고 잘못 써서 10번 넘게 틀렸었다….
처음 코딩할 때 실수하지 않는게 중요한 것 같다.
전체코드
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
vector<vector<int>>arr;
vector<vector<int>>scc_arr;
int discover[10001], scc[10001], country[10001], res[10001];
int cnt, scc_cnt = 1, start, target, n, m, s, t;
stack<int>st;
queue<int>q;
int dfs(int now) {
st.push(now);
discover[now] = cnt++;
int parent = discover[now];
for (int i = 0; i < arr[now].size(); i++) {
int next = arr[now][i];
if (discover[next] == -1)
parent = min(parent, dfs(next));
else if (scc[next] == -1)
parent = min(parent, discover[next]);
}
if (parent == discover[now]) {
while (true) {
int here = st.top();
st.pop();
if (s == here)
start = scc_cnt;
if (t == here)
target = scc_cnt;
scc[here] = scc_cnt;
country[scc_cnt] += 1;
if (here == now)
break;
}
scc_cnt++;
}
return parent;
}
void bfs() {
q.push(start);
res[start] = country[start];
while (!q.empty()) {
int now = q.front();
q.pop();
for (int i = 0; i < scc_arr[now].size(); i++) {
int next = scc_arr[now][i];
if (res[next] < res[now] + country[next]) {
res[next] = res[now] + country[next];
q.push(next);
}
}
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> m >> s >> t;
arr.resize(n + 1);
scc_arr.resize(n + 1);
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b;
arr[a].push_back(b);
}
fill(discover, discover + 10001, -1);
fill(scc, scc + 10001, -1);
for (int i = 1; i <= n; i++) {
if (discover[i] == -1)
dfs(i);
}
for (int now = 1; now <= n; now++) {
for (int i = 0; i < arr[now].size(); i++) {
int next = scc[arr[now][i]];
if (scc[now] != next)
scc_arr[scc[now]].push_back(next);
}
}
if (start == target) {
cout << country[start];
return 0;
}
bfs();
cout << res[target];
return 0;
}