백준 15203번: Police Station (C++)

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

15203번: Police Station

---

Solved By: Tarjan Algorithm

 

각 SCC를 구성하여 SCC의 indegree를 조사합니다. indegree가 0인 SCC가 2개 이상이라면 어떤 행성에서도 모든 행성을 갈 수 없음을 인지한다면 풀 수 있는 문제였습니다.

 

BOJ 4196(https://draw-code-boy.tistory.com/275)과 비슷한 문제였던 거 같습니다.

 

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

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

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

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 indegree_zero_cnt = 0;
    vector<int> res;
    for(int i = 0; i < SCC.size(); i++){
        if(indegree[i] == 0){
            indegree_zero_cnt++;
            for(int j = 0; j < SCC[i].size(); j++){
                res.push_back(SCC[i][j]);
            }
        }
    }
    
    if(indegree_zero_cnt > 1){
        cout << 0; return 0;
    }
    
    sort(res.begin(), res.end());
    cout << res.size() << '\n';
    for(int i = 0; i < res.size(); i++){
        cout << res[i] << ' ';
    }
    
    return 0;
}