Topological Sort

Topological Sort pseudocode:

TOPOLOGICAL-SORT(V, E)

1. Call DFS(V, E) to compute finishing times f[v] for each vertex v
2. When each vertex is finished, insert it onto the front of a linked list
3. Return the linked list of vertices

The graph must be acyclic, Otherwise topological ordering is not possible.

Here is a simple implementatin of Topological Sort:

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define sz 100

vector<int> graph[sz]; //storing the graph
vector<int> topo; //storing the topo ordering
int disc[sz],fin[sz],color[sz];
int time=0;

void dfs_visit(int node)
{
    int i,j,k,temp;
    color[node]=1;
    disc[node]= ++time; //discovery time

    for(i=0;i<graph[node].size();i++)
    {

        temp=graph[node][i];
        if(color[temp]==0)
        {
            dfs_visit(temp);
        }
    }
    color[node]=2;
    fin[node]= ++time; //finishing time
    topo.push_back(node);
}


void dfs(int node)
{
    int i;

    for(i=0;i<node;i++)
    {
        if(color[i]==0)
        {
            dfs_visit(i);
        }
    }
}

int main()
{
    int i,j,k,num,t,node,edge,a,b;

    scanf("%d%d",&node,&edge); //number of node and edges

    for(i=0;i<edge;i++)
    {
        scanf("%d%d",&a,&b);
        graph[a].push_back(b); //directed graph
    }
 
 //initialization
    for(i=0;i<node;i++) color[i]=0;

    dfs(node); //calling dfs to calculate discovery and finishing time
 
 /*
    for(i=0;i<node;i++)
        printf("%d-> %d %d\n",i,disc[i],fin[i]);
 */
 
 //here i use stl vector, so i need to reverse the list
 //using stl list wouldn't need this line
    reverse(topo.begin(),topo.end()); 
 
    printf("Topological Sort:\n");
    for(i=0;i<topo.size();i++)
        printf("%d ",topo[i]);


    return 0;
}