백준 18133번: 가톨릭대학교에 워터 슬라이드를? (C++)

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

18133번: 가톨릭대학교에 워터 슬라이드를??

---

Solved By: Tarjan Algorithm, Topological Sort in SCC

 

진입 차수가 0인 건물 옥상을 구하여 그만큼 카운트해주었습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cmath>
#define MAX 100001
using namespace std;

int n, m;
vector<vector<int>> SCC;
vector<int> adj[MAX];
int visitedOrder[MAX];
int sccnum[MAX];
int indegree[MAX];
stack<int> s;
int order = 0, sccCnt = 0;

int dfs(int now){
    int parent = visitedOrder[now] = ++order;
    s.push(now);
    
    for(int i = 0; i < adj[now].size(); i++){
        int next = adj[now][i];
        
        if(visitedOrder[next] == -1){
            parent = min(parent, dfs(next));
        }
        else if(sccnum[next] == -1){
            parent = min(parent, visitedOrder[next]);
        }
        else{
            indegree[sccnum[next]]++;
        }
    }
    
    if(parent == visitedOrder[now]){
        vector<int> scc;
        
        while(!s.empty()){
            int temp = s.top(); s.pop();
            scc.push_back(temp);
            sccnum[temp] = sccCnt;
            if(now == temp) break;
        }
        
        SCC.push_back(scc);
        if(!s.empty()) indegree[sccCnt]++;
        sccCnt++;
    }
    
    return parent;
}

void tarjan(){
    fill(visitedOrder, visitedOrder + MAX, -1);
    fill(sccnum, sccnum + MAX, -1);
    
    for(int i = 1; i <= n; i++){
        if(visitedOrder[i] == -1){
            dfs(i);
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
    }
    
    tarjan();
    
    int result = 0;
    for(int i = 0; i < sccCnt; i++){
        if(!indegree[i]) result++;
    }
    
    cout << result;
    return 0;
}