Pagini recente » Cod sursa (job #101034) | Cod sursa (job #1150439) | Cod sursa (job #312316) | Cod sursa (job #2200436) | Cod sursa (job #256698)
Cod sursa(job #256698)
//sortare topologica - iterativ
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NMAX 50001
using namespace std;
int *L[NMAX],*L2[NMAX];
int Q[NMAX],grad[NMAX];
int n;
void citire()
{ int i,x,y,m;
FILE *fin=fopen("sortaret.in","r");
fscanf(fin,"%d%d",&n,&m);
for (i=1;i<=n;i++)
{L[i]=(int*)realloc(L[i],sizeof(int)); L[i][0]=0;
L2[i]=(int*)realloc(L2[i],sizeof(int)); L2[i][0]=0;
}
memset(grad,0,(n+1)*sizeof(int));
for (i=1;i<=m;i++)
{
fscanf(fin,"%d%d",&x,&y);
L[x][0]++;
L[x]=(int*)realloc(L[x],(L[x][0]+1)*sizeof(int));
L[x][L[x][0]]=y;
grad[x]++;
L2[y][0]++;
L2[y]=(int*)realloc(L2[y],(L2[y][0]+1)*sizeof(int));
L2[y][L2[y][0]]=x;
}
}
void rez()
{ int i,x,j;
Q[0]=0;
while (Q[0]<n)
{
for (i=1;i<=n;i++)
if (!grad[i])
{
Q[++Q[0]]=i; grad[i]=-1;
for (j=1;j<=L2[i][0];j++)
{
grad[L2[i][j]]--;
}
}
}
}
void afisare()
{int i;
FILE *fout=fopen("sortaret.out","w");
for (i=n;i>0;i--)
fprintf(fout,"%d ",Q[i]);
fclose(fout);
}
int main()
{
citire();
rez();
afisare();
return 0;
}