tosort.cc

#include <vector>
#include <queue>
#include <list>
#include <iostream>

using namespace std;

typedef  pair<int,int> ii;


void addEdge(list<int> *adj,int u, int v)
{
    adj[u].push_back(v);
}

template <int N>
void tsort(list<int> *adj)
{
  vector<int> in(N,0);
  for (int u=0;u<N;u++) {
    list<int>::iterator itr;
    for (itr = adj[u].begin(); itr != adj[u].end();itr++) {
      in[*itr]++;
    }
  }
  
  queue<int> q;
  for (int i=0;i<N;i++) {
    if (in[i] == 0) {
      q.push(i);
    }
  }
  vector<int> result;
  
  int cnt=0;
  while(!q.empty()) {
    int u = q.front();
    q.pop();
    result.push_back(u);
    list<int>::iterator itr;
    for (itr = adj[u].begin();itr != adj[u].end();itr++) {
      if (--in[*itr] == 0) {
        q.push(*itr);
      }
    }
    cnt++;
  }

  for (int i=0; i<result.size(); i++) {
    cout << result[i] << " ";
  }
  cout << endl;
}


int main()
{
  list<int> adj[6];

  addEdge(adj,5,2);
  addEdge(adj,5,0);
  addEdge(adj,4,0);
  addEdge(adj,4,1);
  addEdge(adj,2,3);
  addEdge(adj,3,1);
  
  tsort<6>(adj);

}