Cod sursa(job #677966)

Utilizator tudorsTudor Siminic tudors Data 10 februarie 2012 20:47:09
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <stdio.h>
#include <vector>
#define MAXN 50005
using namespace std;

int n,m,i,a,b;
int D[MAXN],V[MAXN],v;
int x;
vector <int> M[MAXN];
vector <int> :: iterator it;

FILE *f,*g;

int main()
{
	f=fopen("sortaret.in","r");
	g=fopen("sortaret.out","w");
	
	fscanf(f,"%d %d",&n,&m);
	for (i=1;i<=m;++i)
	{
		fscanf(f,"%d %d",&a,&b);
		M[a].push_back(b);
		D[b]++;
	}
	v=0;
	for (i=1;i<=n;++i)
		if (D[i]==0)
			V[++v]=i;
	for (i=1;i<=n;++i)
	{
		x=V[i];
		for (it=M[x].begin();it!=M[x].end();it++)
		{
			D[*it]--;
			if (D[*it]==0)
				V[++v]=(*it);
		}
	}
	for (i=1;i<=n;++i)
		fprintf(g,"%d ",V[i]);
	
	fclose(f);
	fclose(g);
	return 0;
}