백준 4196번: 도미노 (C++)

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

4196번: 도미노

---

Solved By: SCC(Tarjan Algorithm)

 

무너뜨릴 도미노의 최소 개수를 구하는 문제입니다. 도미노들끼리 사이클을 이루고 있을 수도 있습니다. 그러므로 SCC로 묶어서 indegree가 0인 도미노 SCC 그룹들을 개수를 파악하면 풀리는 문제입니다.

 

+SCC관련 문제라는 것을 몰랐다면 꽤 오래 걸렸을 문제입니다.

++DFS를 시키는 범위를 항상 꼭 체크하기.

 

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <memory.h>
#define MAX 100001
using namespace std;

int T;
int n, m;
vector<vector<int>> SCC;
vector<int> adj[MAX];
stack<int> s;
int visitedOrder[MAX];
int sccnum[MAX];
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(true){
            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(){
    // init
    SCC.clear();
    order = 0, sccCnt = 0;
    memset(visitedOrder, -1, sizeof(visitedOrder));
    memset(sccnum, -1, sizeof(sccnum));
    memset(indegree, 0, sizeof(indegree));
    while(!s.empty()) s.pop();
    
    for(int i = 1; i <= n; i++){
        if(visitedOrder[i] == -1) dfs(i);
    }
}

int main(){
    cin >> T;
    while(T--){
        cin >> n >> m;
        
        for(int i = 0; i < MAX; i++) adj[i].clear();
        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] == 0) result++;
        }
        
        cout << result << '\n';
    }
    return 0;
}