fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define mx 200005
  4.  
  5. vector<int>graph[mx];
  6. int visited[mx],start[mx], low[mx];
  7. int timer=1;
  8. stack<int>mystack;
  9. int stack_check[mx];//now all are false
  10. int scc=0;
  11. vector<int>order;
  12. vector<pair<int, int>>backEdge, crossEdge, forwardEdge;
  13.  
  14. void dfs(int node)
  15. {
  16.    visited[node] = 1;
  17.    mystack.push(node);
  18.    stack_check[node] = 1;
  19.    start[node] = timer;
  20.    low[node] = timer;
  21.    timer++;
  22.  
  23.    for(auto child : graph[node])
  24.    {
  25.       if(visited[child] == 0)
  26.       {
  27.          dfs(child);
  28.          low[node] = min(low[node], low[child]);
  29.       }
  30.       else
  31.       {
  32.          if(stack_check[child] == 1)//it is a back-edge
  33.          {
  34.             low[node] = min(low[node], start[child]);
  35.             backEdge.push_back({node, child});
  36.          }
  37.          else
  38.          {
  39.             if(low[node] < low[child]) forwardEdge.push_back({node, child});
  40.             else crossEdge.push_back({node, child});
  41.          }
  42.          //else: it is a cross edge
  43.       }
  44.    }
  45.  
  46.    stack_check[mystack.top()] = 0;
  47.    mystack.pop();
  48.  
  49. }
  50.  
  51. int main(){
  52. #ifndef ONLINE_JUDGE
  53.    freopen("input.txt","r",stdin);
  54.    freopen("output.txt","w",stdout);
  55. #endif
  56.  
  57.    int n,e; cin>>n>>e;
  58.    for(int i=1; i<=e; i++)
  59.    {
  60.        int u,v; cin>>u>>v;
  61.        graph[u].push_back(v);
  62.    }
  63.    for(int i=1; i<=n; i++)
  64.    {
  65.       if(visited[i] == 0)
  66.       {
  67.          dfs(i);
  68.       }
  69.    }
  70.    cout<<"Print all back edges: \n";
  71.    for(auto it : backEdge)cout<<it.first<<' '<<it.second<<endl;
  72.  
  73.    cout<<"Print all cross edges: \n";
  74.    for(auto it : crossEdge)cout<<it.first<<' '<<it.second<<endl; 
  75.  
  76.    cout<<"Print all forward edges: \n";
  77.    for(auto it : forwardEdge)cout<<it.first<<' '<<it.second<<endl; 
  78.  
  79.    cout<<"Print start + minimum start time from n:\n";
  80.    for(int i=1; i<=n;i++)
  81.    {
  82.       cout<<i<<": "<<start[i]<<" - "<<low[i]<<'\n';
  83.    }  
  84.  
  85. }
Success #stdin #stdout 0.01s 11192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Print all back edges: 
Print all cross edges: 
Print all forward edges: 
Print start + minimum start time from n:
1: 1 - 1
2: 2 - 2
https://ideone.com/7kqApQ
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

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!