Cod sursa(job #524838)

Utilizator mvbinfoDragos Dinca mvbinfo Data 23 ianuarie 2011 12:36:01
Problema Sortare topologica Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define dim 50005
using namespace std;

int *A[dim],n,m,i,x,y,viz[dim],r,v[dim],w[dim],nr,in;

int maxim(int a,int b)
{if(a>b)return a;
 return b;}


int dfs(int x)
{int i;
	
	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];


}
void sort(int in,int sf)
{
int i,j,mij,aux;
i=in;
j=sf;
mij=v[(i+j)/2];
do{
	while(v[i]>mij) i++;
	while(v[j]<mij) j--;
	
	if(i<j)
	{aux=v[i]; v[i]=v[j]; v[j]=aux;
	aux=w[i]; w[i]=w[j]; w[j]=aux;}		
	if(i<=j)
		i++,j--; 
 }while(i<=j);
	if(in<j) sort(in,j);
	if(i<sf) sort(i,sf);
}


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;
	w[i]=i;
	}

for(i=1;i<=m;i++)
{
	fscanf(f,"%d %d",&x,&y);
	
	A[x][0]++;
	A[x]=(int* ) realloc(A[x],(A[x][0]+1)*sizeof(int));
	A[x][A[x][0]]=y;
	
	viz[y]=1;
}

for(i=1;i<=n;i++)
	if(viz[i]==0)
		{r=i;break;}
	
memset(viz,0,sizeof(viz));

dfs(r);

sort(1,n);

x=v[1];nr=1;in=1;
v[n+1]=-1;
for(i=2;i<=n+1;i++)
{
	if(v[i]==x)
	{
	nr++;
	}
	else 
	{	if(nr>1)
			sort(in,in+nr-1);
		in=i;
		x=v[i];
		nr=1;	
	}
}

for(i=1;i<=n;i++)
	fprintf(g,"%d ",w[i]);
fprintf(g,"\n");

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