fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. using namespace std;
  5. map<int, int> parent;
  6. void printCycle(int node, int child){
  7.     if(node != child)
  8.         printCycle(parent[node], child);
  9.  
  10.     cout << node <<' ';
  11. }
  12. int timer = 0;
  13. void dfs(int node, vector<vector<int>> &graph, vector<pair<int, int>> &time, map<pair<int, int>, string> &type){
  14.     time[node].first = ++timer;
  15.  
  16.     for(int child: graph[node]){
  17.         parent[child] = node;
  18.         if(!time[child].first){
  19.             type[{node, child}] = "Tree";
  20.             dfs(child, graph, time, type);
  21.         }
  22.  
  23.         else if(!time[child].second)
  24.             type[{node, child}] = "Back";
  25.  
  26.         else if(time[node].first < time[child].first )
  27.              type[{node, child}] = "Forward";
  28.  
  29.         else
  30.              type[{node, child}] = "Cross";
  31.  
  32.     }
  33.  
  34.     time[node].second = ++timer;
  35. }
  36.  
  37. using namespace std;
  38.  
  39. int main(){
  40.  
  41.     int nodes, egdes;
  42.     cin >> nodes >> egdes;
  43.  
  44.     vector<vector<int>> graph(nodes+1);
  45.     vector<pair<int, int>> time(nodes+1); // Arrival & Departure
  46.     map<pair<int, int>, string> type;
  47.  
  48.     int from, to;
  49.     while(egdes--){
  50.         cin >> from >> to;
  51.         graph[from].push_back(to);
  52.     }
  53.  
  54.     // Show Graph
  55.     cout << endl ;
  56.     for(int node = 1; node <= nodes; node++){
  57.         cout << node <<" : ";
  58.         for(int child: graph[node])
  59.             cout << child <<' ';
  60.         cout << endl;
  61.     }
  62.     // dfs
  63.     cout << endl;
  64.     for(int node = 1; node <= nodes; node++)
  65.         if(!time[node].first)
  66.             dfs(node, graph, time, type);
  67.  
  68.     // cycle paths
  69.     cout << endl;
  70.     for(int node = 1; node <= nodes; node++)
  71.         for(auto child: graph[node])
  72.             if(type[{node, child}] == "Back"){
  73.                 printCycle(node, child);
  74.                 cout << child << endl;
  75.             }
  76.  
  77.     return 0;
  78. }
  79.  
Success #stdin #stdout 0s 4380KB
comments (?)
stdin
copy 
6 8
1 1
1 2
2 3
3 4
4 2
2 5
5 6
6 5
stdout
copy 
1 : 1 2 
2 : 3 5 
3 : 4 
4 : 2 
5 : 6 
6 : 5 


1 1
2 3 4 2
5 6 5
https://ideone.com/QIw2vh
Cycle in Graph !
language:
C++14 (gcc 8.3)
created:
5 years 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!