Pagini recente » Cod sursa (job #2002233) | Cod sursa (job #2439596) | Cod sursa (job #1292499) | Cod sursa (job #1709366) | Cod sursa (job #584444)
Cod sursa(job #584444)
#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;
}