Cod sursa(job #545607)

Utilizator algoritmarOvidiu Andrei algoritmar Data 3 martie 2011 18:07:41
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;

#define FIN "sortaret.in"
#define FOUT "sortaret.out"
#define NMAX 50001
#define MMAX 10001

ifstream fin(FIN);
ofstream fout(FOUT);

int deq[NMAX], viz[NMAX];
vector<int> G[NMAX];
int n,m;

void ReadInputs()
{
   int a,b;
   fin >> n >> m;
   for(int i = 1; i <= m; ++i){
	fin >> a >> b;
       	G[a].push_back(b);
	deq[b]++;
   }
}

//n^2
void SolveN2()
{
   for(int i = 1; i <= n; ++i)
      for(int j = 1; j <= n; ++j){
      	if(!viz[j] && !deq[j])
	{
	   viz[j] = 1;
	   fout << j << " " ;
	   for(int k = 0; k < G[j].size(); ++k)
	     deq[ G[j][k] ]--; 
	   break;
       	}
      }
}

int main() 
{
   ReadInputs();
   SolveN2();
   return 0;
}