Cod sursa(job #409906)

Utilizator nautilusCohal Alexandru nautilus Data 3 martie 2010 22:09:24
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<fstream>
#include<vector>
#include<queue>
#define dmax 50002
using namespace std;

vector<long> a[dmax];
queue<long> q;
long grad[dmax];

int main()
{
 long n,m,i,x,y,elem;
	
 ifstream fin("sortaret.in");
 ofstream fout("sortaret.out");
 fin>>n>>m;
 for (i=1; i<=m; i++)
	 {
	  fin>>x>>y;
	  a[x].push_back(y);
	  grad[y]++;
	 }
 
 for (i=1; i<=n; i++)
	 if (grad[i]==0)
		 q.push(i);

 while (q.size())
	 {
	  elem=q.front();
	  
	  fout<<elem<<" ";
	  
	  for (i=0; i<a[elem].size(); i++)
		  {
		   grad[a[elem][i]]--;
		   if (grad[a[elem][i]]==0)
			   q.push(a[elem][i]);
		  }
	  q.pop();
	 }
 
 fin.close();
 fout.close();
 
 return 0;
}