Pagini recente » Cod sursa (job #2572859) | Cod sursa (job #2572818) | Cod sursa (job #1217347) | Cod sursa (job #1168402) | Cod sursa (job #524836)
Cod sursa(job #524836)
#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];
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);
for(i=1;i<=n;i++)
fprintf(g,"%d ",w[i]);
fprintf(g,"\n");
fclose(f);
fclose(g);
return 0;
}