Untitled

mail@pastecode.io avatarunknown
plain_text
2 months ago
885 B
0
Indexable
Never
#include<vector>
#include<stack>


void dfs(int node, vector<vector<int>> &adjlist,vector<bool> &vis,stack<int> &s){

    vis[node]=true;
    for(auto nbr:adjlist[node]){
        if(!vis[nbr]){
            dfs(nbr,adjlist,vis,s);
        }
    }
    s.push(node);
}

vector<int> topologicalSort(vector<vector<int>> &edges, int v, int e)  {
    vector<vector<int>> adjlist(v); //making adj list
    for(int i=0;i<e;i++){   //edges.size()
        int x=edges[i][0];
        int y=edges[i][1];
        adjlist[x].push_back(y);
       // adjlist[y].push_back(x);

    }
    vector<bool> vis(v);
    stack<int> s;
    vector<int> ans;
    for(int i=0;i<v;i++){
        if(!vis[i]){
            dfs(i,adjlist,vis,s);
        }
    }
    while(!s.empty()){
        int num=s.top();
        ans.push_back(num);
        s.pop();

    }
    return ans;
}