C++ :: Topological Sort Algorithm (using DFS)

A topological sort of a dag G = (V,E) is a linear ordering of all its vertices such that if G contains an edge (u,v), then u appears before v in the ordering. (If the graph contains a cycle, then no linear ordering is possible.)

PSEUDOCODE

TOPOLOGICAL-SORT(G)
    call DFS(G) to compute finishing times v.f for each vertex v
    as each vertex is finished, insert it onto the front of a linked list
    return the linked list of vertices

C++ Code

#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <limits>
#define MAX 101
using namespace std;

enum colors {BLACK, WHITE, GRAY};
int color[MAX], d[MAX], p[MAX], f[MAX], t, vertex, edge;
int NIL = numeric_limits<int>::min();

list<int> topoList;
list<int>::iterator it;

list<int> TOPOLOGICAL_SORT(vector<int>[]);
void DFS(vector<int>[]);
void DFS_VISIT(vector<int>[],int);

int main(void)
{
    //freopen("toposort.txt", "r", stdin);
    vector<int> adjList[MAX];
    int u, v;
    cin >> vertex >> edge;
    for(int e=1; e<=edge; e++) {
        cin >> u >> v;
        adjList[u].push_back(v);
    }
    list<int> orderedList = TOPOLOGICAL_SORT(adjList);
    for(it=orderedList.begin(); it != orderedList.end(); ++it) {
        cout << *it << ends;
    }
    return 0;
}

list<int> TOPOLOGICAL_SORT(vector<int> G[]) {
    DFS(G);
    return topoList;
}

void DFS(vector<int> G[]) {
    for(int u=0; u<=vertex; u++) {
        color[u] = WHITE;
        p[u] = NIL;
    }
    t = 0;
    for(int u=1; u<=vertex; u++) {
        if(color[u] == WHITE) {
            DFS_VISIT(G,u);
        }
    }
}

void DFS_VISIT(vector<int> G[], int u) {
    t = t + 1;
    d[u] = t;
    color[u] = GRAY;
    for(int v=0; v<G[u].size(); v++) {
        if(color[G[u][v]] == WHITE) {
            p[G[u][v]] = u;
            DFS_VISIT(G,G[u][v]);
        }
    }
    color[u] = BLACK;
    t = t + 1;
    f[u] = t;
    topoList.push_front(u);
}

Sample Input

9 9
1 2
1 8
2 3
2 8
3 6
4 3
4 5
5 6
7 8

Sample Output

9 7 4 5 1 2 8 3 6

Topological Sort Related UVa Problems

• 124 - Following orders
• 196 - Spreadsheet
• 200 - Rare Order
• 872 – Ordering
• 10305 - Ordering Tasks
• 11060 – Beverages

Refference: Introduction to Algorithms - Thomas H. Cormen