fork(3) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <utility>
  5. #include <string>
  6. using namespace std;
  7. template <typename type>
  8. // 0 means unvisited
  9. // 1 means visited but not finished (still in the stack)
  10. // 2 visited and finished
  11. void DFS( type node, vector<vector<type> > &graph, vector<int> &color,
  12.         map<pair<type, type>, string> &types){
  13.  
  14.     color[node] = 1;
  15. //    for ( auto edge : types )
  16. //        cout << edge.first.first << " " << edge.first.second << " " << edge.second << endl;
  17. //    cout <<  "--------------------------" <<endl;
  18.  
  19.     for( type neighbour : graph[node] ){
  20.         if( color[neighbour] == 0 ) {
  21.             types[{node, neighbour}] = "Tree";
  22.             DFS(neighbour, graph, color, types);
  23.         }
  24.  
  25.         else if( color[neighbour] == 1 ) {
  26.             types[{node, neighbour}] = "Back";
  27.         }
  28.  
  29.         else if( color[neighbour] == 2 ) {
  30.             types[{node, neighbour}] = "Forward/Cross";
  31.         }
  32.     }
  33.  
  34.     color[node] = 2;
  35. }
  36. int main() {
  37.  
  38.     int nodes = 0, edges = 0, cnt = 0;
  39.     cin >> nodes >> edges;
  40.     vector<vector<int> > graph(nodes);
  41.     vector<bool> visited(nodes,false);
  42.     vector<int> color(nodes,0), parent(nodes);
  43.     map<pair<int, int>, string> types;
  44.  
  45.     for( int node = 0; node < edges; node++ ){
  46.         int from, to;
  47.         cin >> from >> to;
  48.         graph[from].push_back(to);
  49.     }
  50. //
  51. //    for( int node = 0; node < nodes; node++ ){
  52. //        cout << node << " : ";
  53. //        for (  auto s : graph[node]) cout << s << " ";
  54. //        cout << "\n";
  55. //    }
  56.     for ( int node = 0; node < nodes; node++ ){
  57.         if( color[node] == 0 ) {
  58.             DFS(node, graph, color, types);
  59.         }
  60.     }
  61.  
  62.     for ( auto edge : types )
  63.         cout << edge.first.first << " " << edge.first.second << " " << edge.second << endl;
  64.     return 0;
  65. }
Success #stdin #stdout 0s 4456KB
comments (?)
stdin
copy 
3 3
0 1
1 2
2 0
stdout
copy 
0 1 Tree
1 2 Tree
2 0 Back
https://ideone.com/wjnbDG
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!