백준 15783번: 세진 바이러스 (C++)

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

15783번: 세진 바이러스

---

Solved By: SCC(Tarjan Algorithm)

 

저번처럼 쓸데없는 메모리는 잡아먹지 않기 위해 필요한 배열들만 선언하여 사용하였습니다.

(https://draw-code-boy.tistory.com/295)

 

기본적인 SCC문제였으며 indegree가 0인 node들을 찾아주면 됩니다.

 

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

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

int dfs(int now){
    int minOrder = visitedOrder[now] = ++order;
    s.push(now);
    
    for(int i = 0; i < adj[now].size(); i++){
        int next = adj[now][i];
        
        if(!visitedOrder[next]) minOrder = min(minOrder, dfs(next));
        else if(!sccNum[next]) minOrder = min(minOrder, visitedOrder[next]);
        else indegree[sccNum[next]]++;
    }
    
    if(visitedOrder[now] == minOrder){
        while(true){
            int temp = s.top(); s.pop();
            sccNum[temp] = sccCnt;
            if(now == temp) break;
        }
        
        if(!s.empty()) indegree[sccCnt]++;
        sccCnt++;
    }
    
    return minOrder;
}

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