Cod sursa(job #2595164)

Utilizator eduard.mieilaMieila Eduard Robert eduard.mieila Data 7 aprilie 2020 11:49:27
Problema Sortare topologica Scor 0
Compilator c-64 Status done
Runda laborator_7_sd_313cab Marime 1.38 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 50000

void dfs_matrix_graph(int matrix[MAXN][MAXN], int node, int Nnodes, int visited[MAXN], int t_fin[MAXN], 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 matrix[MAXN][MAXN];
    int t_desc[MAXN], t_fin[MAXN], *time, visited[MAXN];
    FILE *in, *out;

    for(int i = 0; i < MAXN; i++) {
        for(int j = 0; j < MAXN; j++) {  
            matrix[i][j] = 0;
        }
    }

    in = fopen("sortaret.in", "rt");
    fscanf(in, "%d %d", &nodes, &edges);
    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));
    memset(&t_fin, 0, MAXN);
    memset(&t_desc, 0, MAXN);
    memset(&visited, 0, MAXN);

    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;
}