[C++] 도미노 (백준 4196번)

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

 

첨엔 그냥 scc 개수를 구해서 틀렸다.

 

그런데 1과 2가 같은 scc이고 3과 4가 같은 scc이면서 2에서 3으로 가는 간선이 있는 경우를 생각해보면, scc 개수는 2이지만 답은 1이다.

왜냐하면 1을 넘어뜨리면 같은 scc인 2도 자연스럽게 넘어지고 따라서 3, 4도 넘어지기 때문이다.

 

따라서 이 문제는 scc를 구한 뒤, in-degree가 0인 (다른 것에 의해서 넘어지지 않는) scc의 개수만을 세야 한다.

 

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

vector<vector<int>> adj1;
vector<vector<int>> adj2;
vector<bool> vst;
stack<int> stk;
vector<int> scc;
int idx;

void dfs1(int cur) {
    vst[cur] = true;
    for (int nxt: adj1[cur]) {
        if (!vst[nxt]) dfs1(nxt);
    }
    stk.push(cur);
}

void dfs2(int cur) {
    vst[cur] = true;
    scc[cur] = idx;
    for (int nxt: adj2[cur]) {
        if (!vst[nxt]) dfs2(nxt);
    }
}

void solve() {
    int n, m;
    cin >> n >> m;

    adj1 = vector<vector<int>>(n + 1);
    adj2 = vector<vector<int>>(n + 1);

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        adj1[x].push_back(y);
        adj2[y].push_back(x);
    }

    vst = vector<bool>(n + 1, false);
    for (int i = 1; i < n + 1; i++) {
        if (!vst[i]) dfs1(i);
    }

    vst = vector<bool>(n + 1, false);
    scc = vector<int>(n + 1, -1);
    idx = 0;
    while (!stk.empty()) {
        int x = stk.top();
        stk.pop();
        if (!vst[x]) {
            dfs2(x);
            idx++;
        }
    }

    vector<int> sccin(idx, 0);
    for (int cur = 1; cur < n + 1; cur++) {
        for (int nxt: adj1[cur]) {
            if (scc[cur] != scc[nxt]) {
                sccin[scc[nxt]]++;
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < idx; i++) {
        if (sccin[i] == 0) ans++;
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T = 1;
    cin >> T;
    for (int i = 0; i < T; i++) {
        solve();
    }
}

(AC)