백준 20504번: I번은 쉬운 문제 (C++)

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

20504번: I번은 쉬운 문제

---

Solved By: Tarjan Algorithm, Topological Sort in SCC

 

Tarjan Algorithm을 이용하여 SCC를 구성하고, 각 SCC마다 indegree를 확인하여 0이 아닌 경우에는 다른 함수에 의해 호출될 수 있다는 뜻이므로 방문 배열을 하나 만들어 해당 SCC는 true값을 줍니다. 그리고, 테스트 케이스들을 통해 호출되는 함수들이 구성하는 SCC의 진입 차수가 0일 경우 해당 SCC의 방문 배열을 true값으로 줍니다. 

 

이 작업이 끝나고, 방문 배열을 탐색했을 때 아직 방문하지 않은 곳이 있다면 테스트 케이스를 다 돌려도 호출되지 않았다는 뜻이므로 -1을 출력합니다. 다 방문했을 경우, 최소의 경우이므로 indegree가 0인 SCC를 카운트하여 이 횟수를 출력합니다.

 

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

vector<vector<int>> SCC;
vector<int> adj[MAX];
int visitedOrder[MAX];
int sccnum[MAX];
stack<int> s;
int n, m;
int indegree[MAX];
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(visitedOrder[now] == parent){
        vector<int> scc;
        while(1){
            int temp = s.top(); s.pop();
            scc.push_back(temp);
            sccnum[temp] = sccCnt;
            if(temp == now) 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();
    
    vector<bool> c(sccCnt);
    int check = 0;
    for(int i = 0; i < sccCnt; i++){
        if(indegree[i]) c[i] = true;
        else check++;
    }
    
    int t; cin >> t;
    while(t--){
        int v; cin >> v;
        if(indegree[sccnum[v]] == 0){
            c[sccnum[v]] = true;
        }
    }
    
    bool flag = 1;
    for(int i = 0; i < sccCnt; i++){
        if(c[i] == 0){
            flag = 0;
            break;
        }
    }
    
    if(flag == 1) cout << check;
    else cout << -1;
    
    return 0;
}