13.topologicalSortDFS.md

Topological Sorting

Topological sorting is only possible in DAG i.e directed acyclic graph

• It is not possible in undirected graph, because if there is an edge between 1 and 2, you can't say that 1 should come before 2 or 2 should come before 1
• It is also not possible in directed cyclic graph because

because here you can see that this is directed cyclic graph and we cant say that 2 should come before 3 and 2 sould come before 4 also 4 should come before 2, there is a contardiction, that is why topo sort is used only for DAG

We'd just push the node whose dfs call is over into the stack after marking it as visited, and at last just pop all the elements of the stack and print it.

Time complexity and space complexity

• Time complexity would be O(N+E) as this is using simple DFS
• space complexity would be O(N+E) + O(N) + O(N) + O(N) for adjacency list, vis array, for stack and for DFS call.

0 Based Indexing

#include<bits/stdc++.h>
using namespace std;

void findTopoSort(int node, vector<int> &vis, stack<int> &st, vector<int> adj[]){
    vis[node] = 1;
    for(auto it : adj[node]){
        if(!vis[it]){
            findTopoSort(it, vis, st, adj);
        }
    }
    st.push(node);
}

vector<int> topSort(int v, vector<int> adj[]){
    stack<int> st;
    vector<int> vis(v, 0);
    
    for(int i=0; i<v; i++){
        if(!vis[i]){
            findTopoSort(i, vis, st, adj);
        }
    }
    vector<int> topo;
    while(!st.empty()){
        topo.push_back(st.top());
        st.pop();
    }
    
    return topo;
}
int main(){
    int n, m;
    cin>>n>>m;
    
    vector<int> adj[n];
    for(int i=0; i<m; i++){
        int u, v;
        cin>>u>>v;
        
        adj[u].push_back(v);
    }
    
    vector<int> ans = topSort(n, adj);
    
    for(int i=0; i<ans.size(); i++)
        cout<<ans[i]<<" ";
        
    return 0;
}

1 Based Indexing

#include<bits/stdc++.h>
using namespace std;

void findTopoSort(int node, vector<int> &vis, stack<int> &st, vector<int> adj[]){
    vis[node] = 1;
    for(auto it : adj[node]){
        if(!vis[it]){
            findTopoSort(it, vis, st, adj);
        }
    }
    st.push(node);
}

vector<int> topSort(int v, vector<int> adj[]){
    stack<int> st;
    vector<int> vis(v+1, 0);
    
    for(int i=1; i<=v; i++){
        if(!vis[i]){
            findTopoSort(i, vis, st, adj);
        }
    }
    vector<int> topo;
    while(!st.empty()){
        topo.push_back(st.top());
        st.pop();
    }
    
    return topo;
}
int main(){
    int n, m;
    cin>>n>>m;
    
    vector<int> adj[n+1];
    for(int i=0; i<m; i++){
        int u, v;
        cin>>u>>v;
        
        adj[u].push_back(v);
    }
    
    vector<int> ans = topSort(n, adj);
    
    for(int i=0; i<ans.size(); i++)
        cout<<ans[i]<<" ";
        
    return 0;
}