Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- void toposort(int u){
- ara[u] = 1;
- for(int i=0;i<graph[u].size();i++){
- if(ara[graph[u][i]]==0) toposort(graph[u][i]);
- }
- ara[u] = 2;
- stk.push(u);
- }
- void dfs(int u, int ans){
- ara2[u] = 1;
- for(int i=0;i<rgraph[u].size();i++){
- if(ara2[rgraph[u][i]]==0) dfs(rgraph[u][i], ans);
- }
- ara2[u] = ans;
- }
- int stronglyconnected(int n){
- memset(ara, 0, sizeof ara);
- memset(ara2, 0, sizeof ara2);
- for(int i=1;i<=n;i++) if(!ara[i]) toposort(i);
- int ans = 0;
- while(!stk.empty()){
- if(ara2[stk.top()]==0){
- ans++;
- dfs(stk.top(), ans);
- }
- stk.pop();
- }
- return ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement