Cod sursa(job #404860)

Utilizator alex@ndraAlexandra alex@ndra Data 26 februarie 2010 20:15:15
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<fstream>
#include<vector>
using namespace std;

#define Nmax 50001

vector <int> G[Nmax];
int grad[Nmax],viz[Nmax],sortat[Nmax],n,m;

void citire()
{
	int i,x,y;
	
	ifstream f("sortaret.in");
	   f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y;
		G[x].push_back(y);
	    grad[y]++;
	}
	f.close();
}



	
int main()
{
	int i, j, k,vecini;
	citire();
	
	for(i=1;i<=n;i++)
	{
	  for(j=1;j<=n;j++)
		if(!viz[j]&&grad[j]==0)
		{
		   viz[j]=1;
		   sortat[i]=j;
		   vecini=G[j].size();
		   for(k=0;k<vecini;k++)
			grad[G[j][k]]--;
		   break;
		}
	}
	
	ofstream g("sortaret.out");
	for(i=1;i<=n;i++)
	  g<<sortat[i]<<" ";
	g.close();
	return 0;
}