Cod sursa(job #354763)

Utilizator radu_cppRadu Voroneanu radu_cpp Data 9 octombrie 2009 13:07:07
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <stdio.h>
#include <vector>

using namespace std;

vector<int> a[50010];
vector<int> c;
int grad[50010];
int x,y,i,n,m,j;

int main()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (i=1; i<=m; i++){
		scanf("%d %d",&x,&y);
		grad[y]++;
		a[x].push_back(y);
	}
	for (i=1; i<=n; i++)
		if (!grad[i])
			c.push_back(i);
	for (i=0; i<n; i++){
		printf("%d ",c[i]);
		for (j=0; j<a[c[i]].size(); j++){
			grad[a[c[i]][j]]--;
			if (!grad[a[c[i]][j]])
				c.push_back(a[c[i]][j]);
		}
	}
	return 0;
}