Cod sursa(job #1471011)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 12 august 2015 21:17:28
Problema Sortare topologica Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 0.68 kb
#include<stdio.h>
int n,i,j,k,m,c[50001],*g[50001],a[100002],b[100002],w[50001],v[50001],t;
int C(int g[50001],int n,int x) {
	for(int i=0;i<n;i++)
	if(g[i]==x)
    	return 1;
	return 0;
}
void E(int i) {
	c[i]=1;
	for(int j=w[i]-1;j>=0;j--)
	if(!c[g[i][j]])
    	E(g[i][j]);
	v[++t]=i;
}
int main() {
	freopen("sortaret.in","r",stdin),freopen("sortaret.out","w",stdout),scanf("%d%d",&n,&m);
	for(k=1;k<=m;k++)
    	scanf("%d%d",&a[k],&b[k]),w[a[k]]++;
	for(i=1;i<=n;w[i++]=0)
    	g[i]=new int[w[i]];
	for(k=1;k<=m;k++)
	if(!C(g[a[k]],w[a[k]],b[k]))
    	g[a[k]][w[a[k]]++]=b[k];
	for(i=1;i<=n;i++)
	if(!c[i])
    	E(i);
	for(j=n;j;j--)
    	printf("%d ",v[j]);
}