BOJ 18133 - 가톨릭대학교에 워터 슬라이드를??

BOJ 18133 - 가톨릭대학교에 워터 슬라이드를??

전형적인 SCC 문제이다.

SCC 글을 참고하자.

int n, m;  
vvi edges;  
  
int dfsn = 0;  
stack<int> s;  
vi fin, order, scc_n;  
vvi scc;  
int dfs(int cur) {  
   order[cur] = dfsn++;  
   s.push(cur);  
  
   int low = order[cur];  
  
   for (int to: edges[cur]) {  
      if (fin[to]) continue;  
      if (order[to] == -1) low = min(low, dfs(to));  
      else low = min(low, order[to]);  
   }  
  
   if (low == order[cur]) {  
      vi tmp;  
      while (1) {  
         int nxt = s.top();  
         s.pop();  
         tmp.pb(nxt);  
         fin[nxt] = 1;  
         scc_n[nxt] = sz(scc);  
         if (nxt == cur)break;  
      }  
      scc.pb(tmp);  
   }  
  
   return low;  
}  
  
void solve() {  
   cin >> n >> m;  
   edges = vvi(n);  
   fin = vi(n);  
   order = vi(n, -1);  
   scc_n = vi(n);  
   while (m--) {  
      int u, v;  
      cin >> u >> v;  
      u--, v--;  
      edges[u].pb(v);  
   }  
  
   for (int i = 0; i < n; i++) {  
      if (order[i] == -1) dfs(i);  
   }  
   vi in = vi(sz(scc));  
  
   for (int i = 0; i < n; i++) {  
      for (int j: edges[i]) {  
         if (scc_n[i] != scc_n[j]) {  
            in[scc_n[j]]++;  
         }  
      }  
   }  
   int ans = 0;  
   for (int i = 0; i < sz(scc); i++) {  
      if (in[i] == 0) ans++;  
   }  
   cout << ans;  
}