[백준 4196] 도미노

문제

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

 

알고리즘

SCC

 

풀이

손으로 넘어뜨려야 한다는 것은 자신을 밀어주는 도미노가 없다는 뜻이죠. 그래프로 나타낸다면 자신을 가리키는 간선이 없습니다. 즉, 차수가 0인 컴포넌트의 개수가 정답입니다. SCC를 사용해 그래프를 DAG로 만든 후 모든 간선들을 검사하며 양쪽 정점의 $sccid$가 다르다면 한쪽 정점의 차수를 카운트 해줍니다. 이후 $ind$ 를 순회하며 값이 0이라면 $ans$를 증가시켜주면 됩니다. 

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

int TC,N,M,u,v,VC,SC;

vector<vector<int>> adj;
vector<int> sccid, discovered,ind;
stack<int> st;

int scc(int here) {
    int ret = discovered[here] = VC++;
    st.emplace(here);

    for (auto there : adj[here]) {
        if (discovered[there] == -1) ret = min(ret, scc(there));
        else if (sccid[there] == -1) ret = min(ret, discovered[there]);
    }

    if (ret == discovered[here]) {
        while (1) {
            int t = st.top();
            st.pop();
            sccid[t] = SC;
            if (t == here) break;
        }
        ++SC;
    }
    return ret;
}

int main() {
    FAST;
    cin >> TC;
    while (TC--) {
        cin >> N >> M;

        VC = SC = 0;
        adj.clear();
        sccid.clear();
        discovered.clear();
        adj.resize(N);

        rep(i, M) {
            cin >> u >> v;
            --u, --v;
            adj[u].emplace_back(v);
        }

        sccid = discovered = vector<int>(N, -1);

        rep(i, N) if (discovered[i] == -1) scc(i);

        ind.clear();
        ind.resize(SC);

        rep(here, N) for (auto there : adj[here]) 
            if (sccid[here] != sccid[there]) ++ind[sccid[there]];
        
        int ans = 0;
        rep(i, SC) if (ind[i] == 0) ++ans;
        cout << ans << '\n';
    }

    return 0;
}