fork download
copy 
  1. //
  2. //  main.cpp
  3. //  Topological Sort
  4. //
  5. //  Created by Himanshu on 10/09/21.
  6. //
  7.  
  8. #include <iostream>
  9. #include <vector>
  10. #include <stack>
  11. using namespace std;
  12.  
  13. void printStack (stack<int> st) {
  14.     while(!st.empty()) {
  15.         cout<<st.top()<<" ";
  16.         st.pop();
  17.     }
  18.     cout<<endl;
  19. }
  20.  
  21.  
  22. //n = number of nodes in graph
  23. void topologicalSort (int x, int n, vector<int> graph[], int vis[], stack<int> &st) {
  24.     vis[x] = 1;
  25.     for (int i=0; i<graph[x].size(); i++) {
  26.         int j = graph[x][i];
  27.         if (vis[j] == 0) {
  28.             topologicalSort(j, n, graph, vis, st);
  29.         }
  30.     }
  31.     st.push(x);
  32. }
  33.  
  34.  
  35. int main() {
  36.     int s = 1, n = 6;
  37.     vector<int> graph[n+1];
  38.     int vis[n+1];
  39.     stack<int> st;
  40.  
  41.     graph[1].push_back(2);
  42.     graph[2].push_back(3);
  43.     graph[2].push_back(4);
  44.     graph[3].push_back(4);
  45.     graph[4].push_back(6);
  46.     graph[4].push_back(5);
  47.  
  48.  
  49.     for (int i=1; i<=n; i++) {
  50.         vis[i] = 0;
  51.     }
  52.  
  53.     cout<<"Graph:"<<endl;
  54.     for (int i=1; i<=n; i++) {
  55.         if (graph[i].size() > 0) {
  56.             cout<<i<<": ";
  57.         }
  58.         for (int j=0; j<graph[i].size(); j++) {
  59.             cout<<graph[i][j]<<" ";
  60.         }
  61.         if (graph[i].size() > 0) {
  62.             cout<<endl;
  63.         }
  64.     }
  65.  
  66.     cout<<endl<<"Topological Sort:"<<endl;
  67.     topologicalSort(s, n, graph, vis, st);
  68.     printStack(st);
  69.     return 0;
  70. }
  71.  
Success #stdin #stdout 0s 5516KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Graph:
1: 2 
2: 3 4 
3: 4 
4: 6 5 

Topological Sort:
1 2 3 4 5 6
https://ideone.com/IMygUg
language:
C++14 (gcc 8.3)
created:
3 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!