Cod sursa(job #390553)

Utilizator O_NealS. Alex O_Neal Data 3 februarie 2010 22:46:54
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<stdio.h>
#include<vector>
// N <= 50000
// M <= 100000
using namespace std;

long n,m,gradint[50001]; 
 vector<long> vecini[50001];
 vector<long> sortate; 
 vector<long> farami;

void citire()
{
	long x,y;
	freopen("sortaret.in","r",stdin);
	scanf("%ld %ld",&n,&m);
	for(long i=1; i<=m; i++)
		{
			scanf("%ld %ld",&x,&y);
			vecini[x].push_back(y);
			gradint[y]++;
		}	
}
		
void afisare()
{
	freopen("sortaret.out","w",stdout);
	for(long i=0; i<sortate.size(); i++)
		printf("%ld ", sortate[i]);	
	
}

int main()
{
	
	citire();
	for(long i=1; i<=n; i++)
		if(gradint[i]==0) farami.push_back(i);
	
	while(!farami.empty())
	{
		long nod = farami.back();
		farami.pop_back();
		sortate.push_back(nod);
		while(!vecini[nod].empty())
		{
			long vecin = vecini[nod][0];
			/*
			printf("vecin vizitat: %ld \n", vecin);
			printf("size: %ld\n", vecini[nod].size());
			printf("cei 3 vecini a lui 1: %ld %ld %ld %ld\n", vecini[nod][0],vecini[nod][1],vecini[nod][2],vecini[nod][3]);
			*/
			gradint[vecin]--;
			vecini[nod].erase(vecini[nod].begin());
			if(gradint[vecin]==0) farami.push_back(vecin);
			
			//printf("size: %ld\n", vecini[nod].size());
			//printf("i: %ld\n", i);
		}
	}
	afisare();
	
	return 0;
}