Cod sursa(job #584444)

Utilizator bugyBogdan Vlad bugy Data 25 aprilie 2011 16:08:11
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define dim 50005
using namespace std;

int *A[dim],n,m,i,x,y,v[dim],nr,NR,coada[dim],degr[dim],ok,j;
short int viz[dim];


/*
int dfs(int x)
{int i;
	viz[x]=1;
	for(i=1;i<=A[x][0];i++)
	{
		
		v[ A[x][i] ]=dfs(A[x][i]);
		
		v[x]=maxim(v[A[x][i]]+1,v[x]);
		
	}
	
	return v[x];
}*/


int main()
{
	FILE *f=fopen("sortaret.in","r"), *g=fopen("sortaret.out","w");
	
fscanf(f,"%d %d",&n,&m);

for(i=1;i<=n;i++)
	{A[i]=(int* )realloc(A[i],sizeof(int));
	A[i][0]=0;
	}

for(i=1;i<=m;i++)
{
	fscanf(f,"%d %d",&x,&y);
	
	A[y][0]++;
	A[y]=(int* ) realloc(A[y],(A[y][0]+1)*sizeof(int));
	A[y][A[y][0]]=x;
	
	degr[x]++;
}
ok=1;
while(ok)
{	nr=0;ok=0;
	for(i=1;i<=n;i++)
		if(degr[i]==0&&!viz[i])
			{coada[++nr]=i; ok=1;}
		
	for(i=1;i<=nr;i++)	
	{
	x=coada[i]; viz[x]=1;
	v[++NR]=x;
		for(j=1;j<=A[x][0];j++)
			degr[A[x][j]]--;	
	}
}
for(i=NR;i>=1;i--)
	fprintf(g,"%d ",v[i]);
fprintf(g,"\n");

fclose(f);
fclose(g);
return 0;
}