Cod sursa(job #546119)

Utilizator algoritmarOvidiu Andrei algoritmar Data 4 martie 2011 14:27:31
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 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],Q[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;
       	}
      }
}

//O(N*M)
void Solve()
{ 
   int x;
   vector<int>::iterator it;

   for(int i = 1; i <= n; ++i)	
   	if( deq[i] == 0 ) Q[++Q[0]] = i;
   for(int i = 1; i <= n; ++i){
   	x = Q[i];
	for(it = G[x].begin(); it != G[x].end();it++)
	   {   
		deq[*it]--;
		if( deq[*it] == 0 ) Q[++Q[0]] = *it;
	   }
   }

   for(int i = 1; i <= n; i++)
	fout << Q[i] << " ";
}

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