/Users/jst/src/grafalgo/cpp/graphAlgorithms/misc/toposort.cpp

// usage: toposort
//
// Toposort reads a graph from stdin, and creates an equivalent
// graph whose vertices are in topologically sorted order.
// This graph, and the mapping used to produce, are written
// to stdout.
//
// This program is not bullet-proof. Caveat emptor.

#include "stdinc.h"
#include "Adt.h"
#include "Util.h"
#include "List.h"
#include "Digraph.h"

using namespace grafalgo;

bool toposort(const Digraph&, List&);

int main() {
        Digraph dg; cin >> dg;
        List vlist(dg.n());
        if (toposort(dg,vlist))
                cout << vlist << endl;
        else
                cout << "graph contains cycle\n";
        exit(0);
}

bool toposort(const Digraph& dg, List& vlist) {
        List q(dg.n());
        int *nin = new int[dg.n()+1];

        if (vlist.n() < dg.n()) vlist.resize(dg.n());
        else vlist.clear();

        // Let nin[u]=in-degree of u and put nodes u with nin[u]=0 on q
        for (vertex u = 1; u <= dg.n(); u++) {
                nin[u] = 0;
                for (edge e = dg.firstIn(u); e != 0; e=dg.nextIn(u,e)) {
                        nin[u]++;
                }
                if (nin[u] == 0) q.addLast(u);
        }
        int i = 0;
        while (!q.empty()) { // q contains nodes u with nin[u] == 0
                vertex u = q.first(); q.removeFirst(); vlist.addLast(u); i++;
                for (edge e = dg.firstOut(u); e != 0; e = dg.nextOut(u,e)) {
                        vertex v = dg.head(e);
                        if ((--(nin[v])) == 0) q.addLast(v);
                }
        }
        return (i == dg.n());
}