fork download
copy 
  1. // tarjan by muoii
  2. // vn.spoj.com/problems/TJALG/
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. #define tag "main"
  7. #define maxn 100007
  8. #define forinc(i,a,b) for(int i=a;i<=b;i++)
  9. #define fordec(i,a,b) for(int i=a;i>=b;i--)
  10. #define checkfile(FiLeNaMe) { if(fopen(FiLeNaMe".inp","r")) freopen(FiLeNaMe".inp","r",stdin),freopen(FiLeNaMe".out","w",stdout); }
  11. /// --------------------------------------------------------------------------------------------------------------------------------
  12. #define long long long
  13. int n,m;
  14. vector<int> adj[maxn];
  15.  
  16. // Strong connected components
  17. int scc;
  18. bool dd[maxn];
  19. int num[maxn],low[maxn];
  20. bool deleted[maxn];
  21. stack<int> Stack;
  22. int dfsTime;
  23.  
  24. void dfs(int u) {
  25.     if(dd[u]) return;
  26.  
  27.     dd[u]=1;
  28.     num[u]=low[u]=++dfsTime;
  29.     Stack.push(u);
  30.  
  31.     for(int v : adj[u]) {
  32.         if(deleted[v]) continue;
  33.  
  34.         if(dd[v]) low[u]=min(low[u],num[v]);
  35.         else dfs(v),low[u]=min(low[u],low[v]);
  36.     }
  37.  
  38.     if(low[u]==num[u]) {
  39.         ++scc;
  40.         for(int v = Stack.top();v!=u;v=Stack.top()) Stack.pop(),deleted[v]=1;
  41.         deleted[u]=1;
  42. 		Stack.pop();
  43.     }
  44. }
  45.  
  46. void enter(){
  47.     cin>>n>>m;
  48.  
  49.     for(int i=1,u,v;i<=m;i++) {
  50.         cin>>u>>v;
  51.         adj[u].push_back(v);
  52.     }
  53. }
  54.  
  55. void solve(){
  56.     forinc(i,1,n) dfs(i);
  57.     cout<<scc;
  58. }
  59.  
  60. int32_t main()
  61. {
  62.     checkfile(tag);
  63.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  64.  
  65.     enter();
  66.     solve();
  67.  
  68.     return 0;
  69. }
Success #stdin #stdout 0.01s 6344KB
comments (?)
stdin
copy 
3 2
1 2
2 3
stdout
copy 
3
https://ideone.com/tE7RwB
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!