fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <map>
  5. using namespace std;
  6. vector<int> toplogical;
  7. void topSort(int node, vector<vector<int>> &graph, vector<bool> &visit){
  8.     for(int child: graph[node])
  9.         if(!visit[child]){
  10.             visit[child] = true;
  11.             topSort(child, graph, visit);
  12.             toplogical.push_back(child);
  13.         }
  14. }
  15.  
  16. using namespace std;
  17.  
  18. int main(){
  19.  
  20.     int nodes, egdes;
  21.     cin >> nodes >> egdes;
  22.  
  23.     vector<vector<int>> graph(nodes+1);
  24.     vector<bool> visit(nodes+1);
  25.  
  26.     int from, to;
  27.     while(egdes--){
  28.         cin >> from >> to;
  29.         graph[from].push_back(to);
  30.     }
  31.  
  32.     // Show Graph
  33.     cout << endl ;
  34.     for(int node = 1; node <= nodes; node++){
  35.         cout << node <<" : ";
  36.         for(int child: graph[node])
  37.             cout << child <<' ';
  38.         cout << endl;
  39.     } 
  40.     // dfs
  41.     cout << endl;
  42.     for(int node = 1; node <= nodes; node++)
  43.         if(!visit[node]){
  44.             visit[node] = true;
  45.             topSort(node, graph, visit);
  46.             toplogical.push_back(node);
  47.         }
  48.     // Topological Sort
  49.     reverse(toplogical.begin(), toplogical.end());
  50.     cout << endl;
  51.     for(int node: toplogical)
  52.         cout << node << ' ';
  53.     return 0;
  54. }
Success #stdin #stdout 0s 4268KB
comments (?)
stdin
copy 
7 8
1 2
1 7
2 3
2 4
7 4
3 5
4 5
5 6
stdout
copy 
1 : 2 7 
2 : 3 4 
3 : 5 
4 : 5 
5 : 6 
6 : 
7 : 4 


1 7 2 4 3 5 6
https://ideone.com/ymaLbX
Topological sort
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!