Cod sursa(job #2595147)

Utilizator eduard.mieilaMieila Eduard Robert eduard.mieila Data 7 aprilie 2020 11:35:24
Problema Sortare topologica Scor 0
Compilator c-64 Status done
Runda laborator_7_sd_313cab Marime 1.85 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_desc[MAXN], int t_fin[MAXN], int *time) {
    int i;


    visited[node] = 1;
    t_desc[node] = *time;
    *time = *time + 1;

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

int max_array(int array[], int Nnodes) {
    int max = 0, max_pos = 0;
    for (int i = 1; i <= Nnodes; i++) {
        if (array[i] > max) {
            max = array[i];
            max_pos = i;
        }
    }
    array[max_pos] = 0;

    if (max == 0) {
        return -1;
    } else {
        return max_pos;
    }


}


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_desc, t_fin, time);
        }
    }


    int elem = 0;
    while (elem != -1) {
        elem = max_array(t_fin, nodes);
        if (elem != -1) {
            fprintf(out, "%d ", elem);
        }
    }
    fprintf(in, "\n");



    fclose(out);


    return 0;
}