BOJ 4196 도미노

1 개요

BOJ 4196 도미노

• 백준 온라인 저지 4196번 문제
• BOJ 44단계

2 C++

#include <bits/stdc++.h>
using namespace std;
 
int N, M;
vector<vector<int>> adj;
stack<int> stk;
int vcnt, cnt;
int id[100001];
int indeg[100001];
int discovered[100001];
 
int scc(int cur) {
    int ret = vcnt;
    discovered[cur] = vcnt;
    vcnt++;
    stk.push(cur);
    for(const auto& next: adj[cur]) {
        if(discovered[next] == -1) {
            ret = min(ret, scc(next));
        } else {
            if(id[next] == -1) {
                ret = min(ret, discovered[next]);
            }
        }
    }
    if(ret == discovered[cur]) {
        while(true) {
            int temp = stk.top();
            stk.pop();
            id[temp] = cnt;
            if(temp == cur) break;
        }
        cnt++;
    }
    return ret;
}

void solve() {
    cnt = 0;
    vcnt = 0;
    memset(id, -1, sizeof(id));
    memset(indeg, 0, sizeof(indeg));
    memset(discovered, -1, sizeof(discovered));
    for(int i=1; i<=N; i++) {
        if(discovered[i] != -1) continue;
        scc(i);
    }
    for(int i=1; i<=N; i++) {
        for(const auto& w : adj[i]) {
            if(id[w] == id[i]) continue;
            indeg[id[w]]++;
        }
    }
    int answer = 0;
    for(int i=0; i<cnt; i++) {
        if(indeg[i] == 0) answer++;
    }
    cout << answer << '\n';
}

void sub() {
    cin >> N >> M;
    adj.clear();
    adj.resize(N+1, vector<int>());
    int u, v;
    for(int i=0; i<M; i++){
        cin >> u >> v;
        adj[u].push_back(v);
    }
    solve();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--) {
        sub();
    }
}