[BOJ 4196] 도미노

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

 처음 문제를 풀때는 SCC가 뭔지도 모르고 문제를 풀었었다. 단방향인걸 모르고 양방향이라고 생각하고 Union-find했다가 광탈 

 해당 문제의 경우 SCC를 만들어 주고 해당 SCC로 묶은 그룹내로 들어오는 간선의 개수가 0인 경우를 세주면 되는 문제이다. 솔직히 SCC를 알았어도 삽질+못풀었을수도 있을꺼 같다. (for문에서 i대신 j 써서 진짜 개삽질 한건 ... 근데 웃긴건 앵간한 예제가 다 나왔었다 ㅋㅋ... )

 일단 문제의 경우 코사라주 알고리즘을 통해 각각 SCC를 만들어 주고 해당 정점이 어떤 SCC 그룹에 속하는지 기록해 둔다. 그 이후 모든 SCC 그룹에서 다른 그룹으로 가는 간선의 경우를 세주면 되는 문제이다.  

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <set>
#include <queue>
#include <stack>
#define MAX_N 100000
typedef long long ll;
 
using namespace std;
 
int t,n,m,num,scc[MAX_N+1],in[MAX_N+1];
vector<vector<int>> vt;
vector<vector<int>> rvt;
stack<int> st;
bool visit[MAX_N+1];
 
void dfs(int x){
    visit[x] = true;
    for(int i=0;i<vt[x].size();i++){
        int next = vt[x][i];
        if(!visit[next]){
            visit[next] = true;
            dfs(next);
        }
    }
    st.push(x);
}
 
void func(int x){
    visit[x] = true;
    scc[x] = num;
    
    for(int i=0;i<rvt[x].size();i++){
        int next = rvt[x][i];
        if(!visit[next]){
            visit[next] = true;
            func(next);
        }
    }
}
 
int main(){
    cin >> t;
    while(t--){
        memset(scc,0,sizeof(scc));
        memset(in,0,sizeof(in));
        vt.clear();
        rvt.clear();
        cin >> n >>m;
        vt.resize(n+1);
        rvt.resize(n+1);
        
        for(int i=1;i<=m;i++){
            int a,b;
            cin >> a>>b;
            vt[a].push_back(b);
            rvt[b].push_back(a);
        }
        memset(visit,false,sizeof(visit));
        
        for(int i=1;i<=n;i++){
            if(!visit[i]){
                dfs(i);
            }
        }
        
        memset(visit,false,sizeof(visit));
        
        num = 1;
        while(!st.empty()){
            int t = st.top();
            st.pop();
            if(!visit[t]){
                func(t);
                num++;
            }
        }
        
        for(int i=1;i<=n;i++){
            for(int j=0;j<vt[i].size();j++){
                int next = vt[i][j];
                if(scc[i] != scc[next]){
                    in[scc[next]]++;
                }
                
            }
        }
        int ans = 0;
        for(int i=1;i<num;i++){
            if(in[i] == 0){
                ans++;
            }
        }
        cout <<ans <<endl;
    }
    
    return 0;
}