Cod sursa(job #444266)

Utilizator drywaterLazar Vlad drywater Data 19 aprilie 2010 21:12:16
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <stdio.h>
#include <cstring>
#include <vector>
#define pb push_back
using namespace std;
FILE *f=fopen("sortaret.in","r"),*g=fopen("sortaret.out","w");
int q[50050],n,m,i,a,b,deg[50050]; 
vector<int> L[50050];
int main(void)
{
	vector<int>::iterator j;
	fscanf(f,"%d%d",&n,&m);
	for (i=1;i<=m;i++)
	{
		fscanf(f,"%d%d",&a,&b);
		L[a].pb(b);
	}
	for (i=1;i<=n;i++)
	{
		if (deg[i]==0)
			q[++q[0]]=i;
	}
	for (i=1;i<=n;i++)
	{
		fprintf(g,"%d ",q[i]);
		for (j=L[i].begin();j!=L[i].end();j++)
		{
			deg[*j]--;
			if (deg[*j]==0)
				q[++q[0]]=*j;
		}
	}
	fprintf(g,"\n");
	fclose(g);
	return 0;
}