백준 4196 도미노 C++

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

 

SCC를 활용한 문제입니다. 

 

도미노 관계가 주어졌을 때, 최소 몇 개의 도미노를 넘어트려야 전체 도미노가 쓰러지는 지를 계산합니다. 

 

SCC를 계산하면, 각 SCC는 사이클을 이루므로 아무거나 넘어트려도 됩니다. 

 

그리고 SCC를 구성하는 컴포넌트들을 하나의 큰 노드로 본다면, 그 노드들 중 indegree 엣지가 0인 것들만 넘어트린다면 전체가 넘어지고, 이것이 최소 개수입니다. 

 

indegree 엣지가 0인 것들은, 입력된 그래프의 엣지를 대상으로, from, to 노드가 동일 컴포넌트인지 아닌지를 체크하면 알 수 있습니다. 

즉, 컴포넌트 번호가 다르다면, 엣지로 연결된 두 노드는 다른 컴포넌트에 있는 것이고, 이는 to 노드가 포함된 컴포넌트의 indegree가 있는 것입니다. 

 

코드는 다음과 같습니다. 

#include <iostream>
#include <vector>
#include <stack>
#include <cstring>

using namespace std;

int T;
int N, M;
vector<vector<int>> graph;
vector<vector<int>> invGraph;
vector<bool> visited;

// scc 중 indegree 0 인 거 개수가 정답 
// scc면 어짜피 그 안에서 아무거나 쓰러트려도 되고, scc 간 연결로 이어진 다른 scc도 쓰러짐 

void init() {
    cin >> N >> M;

    graph.clear();
    graph.resize(N+1);
    invGraph.clear();
    invGraph.resize(N+1);
    visited.clear();
    visited.resize(N+1);

    int from, to;
    for(int i = 0; i < M; i++) {
        cin >> from >> to;
        graph[from].push_back(to);
        invGraph[to].push_back(from);
    }
}

void dfs(int node, stack<int> &stk) {
    if(visited[node]) return;

    visited[node] = true;
    for(auto v : graph[node]) {
        if(visited[v]) continue;
        dfs(v, stk);
    }

    stk.push(node);
}

void invDfs(int node, vector<int> &vec) {
    if(visited[node]) return;

    visited[node] = true;
    vec.push_back(node);

    for(auto v : invGraph[node]) {
        if(visited[v]) continue;
        invDfs(v, vec);
    }
}

int calc() {
    int result = 0;

    stack<int> stk;
    for(int i = 1; i <= N; i++) {
        dfs(i, stk);
    }

    visited.clear();
    visited.resize(N+1);
    vector<vector<int>> scc;
    while(!stk.empty()) {
        int node = stk.top();
        stk.pop();

        vector<int> vec;
        invDfs(node, vec);
        if(vec.size() > 0) scc.push_back(vec);
    }

    // scc 1개면 통채로 사이클인 경우
    if(scc.size() == 1) {
        result = 1;
        return result;
    }

    // scc 구성된 것 중 indegree 0 인 거 구하기 
    // scc로 묶인 거는 같은 노드 간주
    // 기존에 엣지 기준으로 같은 노드 아니면 컴포넌트 간 엣지 있는 거
    vector<int> inDegree;
    inDegree.resize(scc.size());

    vector<int> components;
    components.resize(N + 1);

    // 몇 번째 컴포넌트인지 계산
    for(int i = 0; i < scc.size(); i++) {
        for(auto v : scc[i]) {
            components[v] = i;
        }
    }

    // 기존 엣지 대상으로 같은 컴포넌트인지 계산 
    for(int i = 1; i <= N; i++) {
        for(auto v : graph[i]) {
            if(components[i] != components[v]) {
                inDegree[components[v]]++;
            }
        }
    }

    // indegree 0 인 거 개수 
    for(auto v : inDegree) {
        if(v == 0) result++;
    }

    return result;
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> T;
    while(T--) {
        init();
        int result = calc();
        cout << result << '\n';
    }
}