//
//  main.cpp
//  Topological Sort
//
//  Created by Himanshu on 10/09/21.
//

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void printStack (stack<int> st) {
    while(!st.empty()) {
        cout<<st.top()<<" ";
        st.pop();
    }
    cout<<endl;
}


//n = number of nodes in graph
void topologicalSort (int x, int n, vector<int> graph[], int vis[], stack<int> &st) {
    vis[x] = 1;
    for (int i=0; i<graph[x].size(); i++) {
        int j = graph[x][i];
        if (vis[j] == 0) {
            topologicalSort(j, n, graph, vis, st);
        }
    }
    st.push(x);
}


int main() {
    int s = 1, n = 6;
    vector<int> graph[n+1];
    int vis[n+1];
    stack<int> st;
    
    graph[1].push_back(2);
    graph[2].push_back(3);
    graph[2].push_back(4);
    graph[3].push_back(4);
    graph[4].push_back(6);
    graph[4].push_back(5);

    
    for (int i=1; i<=n; i++) {
        vis[i] = 0;
    }
    
    cout<<"Graph:"<<endl;
    for (int i=1; i<=n; i++) {
        if (graph[i].size() > 0) {
            cout<<i<<": ";
        }
        for (int j=0; j<graph[i].size(); j++) {
            cout<<graph[i][j]<<" ";
        }
        if (graph[i].size() > 0) {
            cout<<endl;
        }
    }
    
    cout<<endl<<"Topological Sort:"<<endl;
    topologicalSort(s, n, graph, vis, st);
    printStack(st);
    return 0;
}