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


1 -> 1 is Back
1 -> 2 is Tree
1 -> 4 is Tree
1 -> 5 is Forward
2 -> 3 is Tree
3 -> 2 is Back
4 -> 2 is Cross
4 -> 5 is Tree
https://ideone.com/vt8RQE
Type of Graph Edges
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!