Cod sursa(job #2595193)

Utilizator eduard.mieilaMieila Eduard Robert eduard.mieila Data 7 aprilie 2020 12:08:04
Problema Sortare topologica Scor 50
Compilator c-64 Status done
Runda laborator_7_sd_313cab Marime 1.37 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 50001

void dfs_matrix_graph(char **matrix, int node, int Nnodes, char *visited, int *t_fin, int *time) {
    int i;


    visited[node] = 1;

    for (i = 0; i <= Nnodes; i++) {
        if (matrix[node][i] == 1 && visited[i] == 0) {
            dfs_matrix_graph(matrix, i, Nnodes, visited, t_fin, time);
        }
    }
    t_fin[*time] = node;
    *time = *time + 1;
}




int main() {
    int nodes, edges, x, y;
    int *t_fin, *time;
    FILE *in, *out;
    char **matrix, *visited;

    

    in = fopen("sortaret.in", "rt");
    fscanf(in, "%d %d", &nodes, &edges);
    
    visited = calloc(nodes + 1, sizeof(char));
    t_fin = calloc(nodes + 1, sizeof(int));
    matrix = calloc(nodes + 1, sizeof(char*));

    for (int i = 0; i <= nodes; i++) {
        matrix[i] = calloc(nodes + 1, sizeof(char));
    }
    
    for (int i = 1; i <= edges; i++) {
        fscanf(in, "%d %d", &x, &y);
        matrix[x][y] = 1;
    }
    fclose(in);

    out = fopen("sortaret.out", "wt");
    time = calloc(1, sizeof(int));

    for (int i = 1; i <= nodes; i++) {
        if (visited[i] == 0) {
            dfs_matrix_graph(matrix, i, nodes, visited, t_fin, time);
        }
    }

    for (int i = nodes - 1; i >= 0; i--) {
        fprintf(out, "%d ", t_fin[i]);
    }
    fprintf(out, "\n");



    fclose(out);


    return 0;
}