Pagini recente » Cod sursa (job #1357921) | Cod sursa (job #2797874) | Cod sursa (job #23913) | Cod sursa (job #2511152) | Cod sursa (job #524838)
Cod sursa(job #524838)
#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;
}