Pagini recente » Cod sursa (job #256923) | Cod sursa (job #698217) | Cod sursa (job #2552206) | Cod sursa (job #785704) | Cod sursa (job #2615365)
#include <stdio.h>
#include <stdlib.h>
int SortareTopologica(int n, int *vizitat, int **MatriceAd, int *sortare,int *ok,int N)
{
vizitat[n] = 1;
int i;
for(i = 1; i < N+1; i++)
{
if(MatriceAd[n][i] == 1 && i != n)
{
if(vizitat[i] == 1)
{
return 0;
}
if(vizitat[i] == 0)
{
if(SortareTopologica(i,vizitat,MatriceAd,sortare,ok,N) == 0)
{
return 0;
}
}
}
}
sortare[(*ok)] = n;
*ok += 1;
vizitat[n] = -1;
return 1;
}
int main()
{
FILE *input = fopen("sortaret.in","rt");
FILE *output = fopen("sortaret.out","wt");
int N,M,i;
fscanf(input,"%d %d\n",&N,&M);
int ** MatriceAd = (int**) malloc(sizeof(int*)*(N+1));
for(i = 0; i < N+1; i++)
{
MatriceAd[i] = (int*) calloc(N+1,sizeof(int));
}
int s, d;
for(i = 0; i < M; i++)
{
fscanf(input,"%d %d\n",&s,&d);
MatriceAd[s][d] = 1;
}
int *vizitat = (int*) calloc(N+1,sizeof(int));
int *sortare = (int*) calloc(N+1,sizeof(int));
int ok = 1;
SortareTopologica(1,vizitat,MatriceAd,sortare,&ok,N);
for(i = N; i >= 1; i--)
{
if(i != N) fprintf(output," ");
fprintf(output,"%d",sortare[i]);
}
fclose(input);
fclose(output);
for(i = 0; i < M; i++)
{
free(MatriceAd[i]);
}
free(MatriceAd);
return 0;
}