[백준 2152번] 여행 계획 세우기

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

여행 계획 세우기 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	1532	287	151	14.632%

문제

평소 일로 바쁘던 태희는 휴가를 통해 여행을 다녀오기로 하였다. 우선 태희는 사전 조사를 통해서 여행하려는 도시를 N(1≤N≤10,000)개 선택하였다. 태희는 비행기를 이용하면 충분히 여행할 수 있을거라 생각했지만, 짐을 꾸리던 중 비행기가 모든 도시들 사이를 다니는 것은 아님을 알게 되었다.

태희는 다시 비행로에 대해 조사를 하였고, 총 M(1≤M≤100,000)개의 비행로가 존재함을 알게 되었다. 각각의 비행로는 한 방향으로의 서비스만을 제공한다. 태희는 S(1≤S≤N)번 도시에서 시작해서 T(1≤T≤N)번 도시에서 여행을 끝내기로 하였다. 그리고 태희는 도시와 항공로에 대한 정보를 바탕으로 여행 계획을 세우기로 하였다.

도시와 비행로에 대한 정보가 주어졌을 때, S번 도시에서 T번 도시로 여행을 할 때 최대로 방문할 수 있는 도시의 개수를 구하는 프로그램을 작성하시오. 각각의 도시는 여행 중에 몇 번이든 방문할 수 있으며, 같은 항공로를 여러 번 이용할 수도 있다. 물론 같은 도시를 여러 번 방문하는 경우는 한 번만 생각하기로 한다.

입력

첫째 줄에 네 정수 N, M, S, T가 주어진다. 다음 M개의 줄에는 각각의 비행로에 대한 정보를 나타내는 서로 다른 두 정수 A, B(1≤A, B≤N)가 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 항공로가 존재함을 의미한다.

출력

첫째 줄에 방문할 수 있는 도시의 최대 개수를 출력한다. 만약 여행 계획을 목표대로 세울 수 없다면 0을 출력한다.

예제 입력 1 

3 4 1 1
1 2
2 3
3 2
2 1

예제 출력 1 

3

SCC 문제이다. 바로 전에 해결한 ATM문제랑 거의 똑같다고 보면 된다.

위상정렬과 더불어 복습을 많이 해야할듯싶다. ATM과 같은 유형이니 설명은 생략한다.

#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
 
using namespace std;
 
int numbering[10001], cnt,scc_numbering[10001],SCC_num = 1;
bool finished[10001];
stack<int> sta;
 
int N,M,S,T,A,B;
vector<int> v[10001], v0[10001];
int scc_indegree[10001], indegree[10001], scc_cnt[10001], scc_cnt0[10001];
bool cal[10001];
queue<int> q;
 
int dfs(int);
 
int main(){
 
    ios::sync_with_stdio(false);
 
    cin >> N >> M >> S >> T;
 
    for(int i=0;i<M;i++){
        cin >> A >> B;
        v[A].push_back(B);
    }
 
    for(int i=1;i<=N;i++){
        if(numbering[i] == 0) dfs(i);
    }
 
    S = scc_numbering[S];
 
    for (int i = 1; i <= N; i++) {
        for (int j : v[i]) {
            if (scc_numbering[i] == scc_numbering[j]) continue;
            v0[scc_numbering[i]].push_back(scc_numbering[j]);
            scc_indegree[scc_numbering[j]]++;
        }
    }
 
    for (int i = 1; i < SCC_num; i++) {
        scc_cnt0[i] = scc_cnt[i];
        if (i == S) cal[i] = true;
        if (scc_indegree[i] == 0) q.push(i);
    }
 
    while (!q.empty()) {
        int num = q.front();
        q.pop();
 
        for (int i = 0; i < v0[num].size(); i++) {
            if (cal[num]) {
                scc_cnt0[v0[num][i]] = max(scc_cnt0[v0[num][i]],scc_cnt0[num] + scc_cnt[v0[num][i]]);
                cal[v0[num][i]] = true;
            }
 
            if (--scc_indegree[v0[num][i]] == 0) q.push(v0[num][i]);
        }
    }
 
    if(!cal[scc_numbering[T]]) cout << "0";
    else cout << scc_cnt0[scc_numbering[T]];
 
    return 0;
}
 
int dfs(int num) {
 
    numbering[num] = ++cnt;
    sta.push(num);
 
    int result = numbering[num];
    for (int i : v[num]) {
        if (numbering[i] == 0) result = min(result, dfs(i));
        else if (!finished[i]) result = min(result, numbering[i]);
    }
 
    if (result == numbering[num]) {
        while (1) {
            int t = sta.top();
            sta.pop();
            finished[t] = true;
            scc_numbering[t] = SCC_num;
            scc_cnt[SCC_num]++;
            if (t == num) break;
        }
        SCC_num++;
    }
    return result;
}