문제

https://www.acmicpc.net/problem/2152


알고리즘

SCC


풀이

SCC는 그래프를 DAG로 바꾸며 각 컴포넌트의 크기를 최대로 묶어줍니다.

최대 도시를 구한다는 점과 시작 도시와 도착 도시가 있다는 점은 SCC와 잘 어울리죠. DAG로 그래프를 바꾼 후에는 DAG상에서 차수가 낮은 컴포넌트부터 차수가 높은 컴포넌트를 갱신해줍니다. 즉 위상정렬 순서로 갱신해줍니다. 유의할 점 중 하나는 SCC알고리즘을 사용하게 되면 $sccid$의 역순이 위상 정렬 순서와 동일합니다. 다시 말해 $sccid$ 의 값이 작다면 위상정렬 순서상 뒤에 있고, $sccid$값이 크다면 위상 정렬순서상 앞에 있음을 의미합니다. 굳이 위상 정렬 알고리즘을 사용해서 순서를 배치할 필요가 없습니다. dfs 한 번을 사용하여 풀 수 있으므로 시간 복잡도는 $O(V+E)$입니다.

코드

#include <bits/stdc++.h>
#include <unordered_set>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

int N, M, S, T,u,v,SC,VC;

vector<vector<int>> adj;
vector<vector<int>> sccadj;
int discovered[10001],sccid[10001],cache[10001],sccSIZE[10001];
stack<int> st;

int scc(int here) {
    int ret = discovered[here] = VC++;
    st.emplace(here);
    for (auto there : adj[here]) {
        if (discovered[there] == -1) ret = min(ret, scc(there));
        else if (sccid[there] == -1) ret = min(ret, discovered[there]);
    }

    if (ret == discovered[here]) {
        int SIZE = 0;
        while (1) {
            int t = st.top();
            st.pop();
            sccid[t] = SC;
            ++SIZE;
            if (t == here) break;
        }
        sccSIZE[SC] = SIZE;
        SC++;
    }
    return ret;
}

int main() {
    FAST;
    memset(discovered, -1, sizeof(discovered));
    memset(sccid, -1, sizeof(sccid));

    cin >> N >> M >> S >> T;
    --S, --T;
    adj.resize(N);
    rep(i, M) {
        cin >> u >> v;
        --u, --v;
        adj[u].emplace_back(v);
    }

    rep(i, N) if (discovered[i] == -1) scc(i);

    sccadj.resize(SC);
    rep(i, N) {
        for (auto j : adj[i]) {
            if (sccid[i] != sccid[j])
                sccadj[sccid[i]].emplace_back(sccid[j]);
        }
    }
    S = sccid[S];
    T = sccid[T];

    memset(cache, -0x3f, sizeof(cache));
    cache[S] = sccSIZE[S];
    for (int i = S;i >= T;--i) {
        if (cache[i] < 0) continue;
        for (int j : sccadj[i])
            cache[j] = max(cache[j], cache[i] + sccSIZE[j]);
    }

    cout << (cache[T]<0?0:cache[T]);
    return 0;
}