topological_sort.cpp

// Directed Acyclic GRAPH
// Topological sort
// vertices start from 1 onwards
#include <bits/stdc++.h>
using namespace std;

class Graph{
    int vertices;
    vector<int>*adj;
    bool cycle=false;
    int *visited;
    stack<int>stk;
public:
    Graph(int v);
    ~Graph(){
        delete [] adj;
        delete [] visited;
        cout<<"\n";
    }
    void addedge(int a,int b);
    void visit_false();
    void dfs_util(int s);
    void topological_sort();
};
Graph::Graph(int v){
    vertices=v;
    adj=new vector<int>[v];
    visited=new int[v];
}
void Graph::addedge(int a,int b){
    adj[a].push_back(b);
}
void Graph::visit_false(){
    for(int i=0;i<vertices;i++){
        visited[i]=0;
    }
}
void Graph::dfs_util(int s){
    if(cycle){
        return;
    }
    if(visited[s]==1){
        cycle=true;
        return;
    }
    if(visited[s]==2){
        return;
    }
    // cout<<s+1<<" ";
    visited[s]=1;
    for(auto u: adj[s]){
        if(cycle){
            return;
        }
        dfs_util(u);
    }
    stk.push(s);
    visited[s]=2;
}
void Graph::topological_sort(){
    visit_false();
    for(int i=0;i<vertices;i++){
        if(visited[i]==2){
            continue;
        }
        if(cycle){
            break;
        }
        dfs_util(i);
    }
    if(cycle){
        cout<<"there is a cycle,topological sort not possible\n";
        return;
    }
    while(!stk.empty()){
        cout<<stk.top()+1<<" ";
        stk.pop();
    }
}

int main() {
    int vertices,edges;
    cout<<"Enter no of vertices & edges\n";
    cin>>vertices>>edges;
    Graph g(vertices);
    cout<<"Enter pair of adjacent vertices\n";
    for(int i=0;i<edges;i++){
        int a,b;
        cin>>a>>b;
        g.addedge(a-1,b-1);
    }
    cout<<"topological sort\n";
        g.topological_sort();

	return 0;
}