Cod sursa(job #2615365)

Utilizator iuliandraceaDracea Iulian-Ilie iuliandracea Data 14 mai 2020 15:01:51
Problema Sortare topologica Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#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;
}