[BOJ] 2152 : 여행 계획 세우기

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
const int MAXN = 1e4 + 10;

int n, m, s, e;
int cnt, pos, scc[MAXN], chk[MAXN], stk[MAXN];
vi gph[MAXN];
vector<vi> res;

int dfs(int now) {
	chk[now] = ++cnt;
	int ret = chk[now];
	stk[pos++] = now;
	for (int nxt : gph[now]) {
		if (!chk[nxt]) ret = min(ret, dfs(nxt));
		else if (!scc[nxt]) ret = min(ret, chk[nxt]);
	}

	if (ret != chk[now]) return ret;

	res.push_back(vi());
	while (1) {
		int top = stk[--pos];
		scc[top] = res.size();
		res[scc[top] - 1].push_back(top);
		if (top == now) break;
	}

	return ret;
}

set<int> adj[MAXN];

int main() {
	scanf("%d %d %d %d", &n, &m, &s, &e);
	for (int i = 1; i <= m; i++) {
		int u, v; scanf("%d %d", &u, &v);
		gph[u].push_back(v);
	}

	for (int i = 1; i <= n; i++)
		if (!chk[i]) dfs(i);

    for (int i = 1; i <= n; i++) {
        for (int it : gph[i]) {
            if (scc[i] != scc[it]) {
                adj[scc[i]].insert(scc[it]);
            }
        }
    }

    vector<int> d(n+1);
    s = scc[s];
    e = scc[e];
    d[s] = res[s-1].size();
    for (int i = s; i >= e; i--) {
        for (int it : adj[i]) {
            d[it] = max(d[it], d[i]+(int)res[it-1].size());
        }
    }

    printf("%d\n", d[e]);

	return 0;
}