// GraphAlgorithms.cpp - wdg - 2008
// Using Java style!
#include "Dag.h"
#include "IntQueue.h"

#include <iostream>
using namespace std;

class GraphAlgorithms 
{
    public: 
    static string topologicalSort(const DAG & dag) 
    {
       int N = dag.numberVertices();
       int inDeg[N];
       for(int i=0; i<N; i++)
           inDeg[i] = dag.inDegree(i);

       IntQueue Q(N);
       for(int j=0; j<N; j++)
         if( inDeg[j]==0 )
             Q.enqueue( j );

       string S;
       while ( !Q.isEmpty() ) {
          int curr = Q.dequeue();
          S += curr+'0';
          S += " ";
          for(int j=0; j<N; j++) 
            if( dag.isAdjacent(curr,j) ) {
                inDeg[j]--;
                if( inDeg[j]==0 )
                   Q.enqueue(j);
            }
       }

       return S;          
    }
};