Advertisement
Jasir

strongly connected component

Jun 12th, 2018
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.69 KB | None | 0 0
  1. void toposort(int u){
  2.     ara[u] = 1;
  3.     for(int i=0;i<graph[u].size();i++){
  4.         if(ara[graph[u][i]]==0) toposort(graph[u][i]);
  5.     }
  6.     ara[u] = 2;
  7.     stk.push(u);
  8. }
  9.  
  10. void dfs(int u, int ans){
  11.     ara2[u] = 1;
  12.     for(int i=0;i<rgraph[u].size();i++){
  13.         if(ara2[rgraph[u][i]]==0) dfs(rgraph[u][i], ans);
  14.     }
  15.     ara2[u] = ans;
  16. }
  17.  
  18. int stronglyconnected(int n){
  19.     memset(ara, 0, sizeof ara);
  20.     memset(ara2, 0, sizeof ara2);
  21.     for(int i=1;i<=n;i++) if(!ara[i]) toposort(i);
  22.     int ans = 0;
  23.     while(!stk.empty()){
  24.         if(ara2[stk.top()]==0){
  25.             ans++;
  26.             dfs(stk.top(), ans);
  27.         }
  28.         stk.pop();
  29.     }
  30.     return ans;
  31. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement