Cod sursa(job #2595130)

Utilizator razvan.ursatanuUrsatanu Razvan razvan.ursatanu Data 7 aprilie 2020 10:55:40
Problema Sortare topologica Scor 100
Compilator c-64 Status done
Runda laborator_7_sd_313cab Marime 2.13 kb
#include <stdio.h>
#include <stdlib.h>
#define NMAX 100001

typedef struct Node {
    void *data; 
    struct Node *next;
} Node;
 
typedef struct {
    Node *head;
    Node *tail;
    int size;
} LinkedList;
 
typedef struct {
    LinkedList **neighbors;
    int nodes;
} ListGraph;
 
void init_list_graph(ListGraph *graph, int nodes) {
    graph->nodes = nodes;
    graph->neighbors = malloc((nodes+1) * sizeof(LinkedList*));
    for(int i = 1; i <= nodes; ++i) {
        graph->neighbors[i] = malloc(sizeof(LinkedList));
        graph->neighbors[i]->head = NULL;
        graph->neighbors[i]->tail = NULL;
        graph->neighbors[i]->size = 0;
    }
}
 
void add_edge_list_graph(ListGraph *graph, int src, int *dest) {
    Node *nod;
    nod = malloc(sizeof(Node));
    nod->data = dest;
    nod->next = NULL;
    Node *p;
    p = graph->neighbors[src]->head;
    if(p == NULL) {
        graph->neighbors[src]->head = nod;
        graph->neighbors[src]->tail = nod;
        graph->neighbors[src]->size++;
        return;
    }
    while(p->next != NULL) {
        p = p->next;
    } 
    p->next = nod;
    graph->neighbors[src]->tail = nod;
    graph->neighbors[src]->size++;
}
 
void dfs_list_graph(ListGraph *lg, int node, int *visited, int *v, int *num) {
	Node *p;
    p = lg->neighbors[node]->head;
    visited[node] = 1;
    while(p != NULL) {
        if(visited[*(int*)p->data] == -1){
             dfs_list_graph(lg, *(int*)p->data, visited, v, num);
        }
        p = p->next;
    }
    v[++(*num)] = node;
}
 
int main() {
	int n, m, num = 0, x[NMAX], y[NMAX], visited[NMAX], v[NMAX];
	ListGraph *lg;
	lg = malloc(sizeof(ListGraph));
	FILE *in1 = fopen("sortaret.in", "rt");
	FILE *out1 = fopen("sortaret.out", "wt");
	fscanf(in1, "%d%d", &n, &m);
	init_list_graph(lg, n);
	for(int i = 1; i <= m; ++i){
		fscanf(in1, "%d%d", &x[i], &y[i]);
	}
	for(int i = 1; i <= m; ++i){
		add_edge_list_graph(lg, x[i], &y[i]);
	}
	for(int i = 1; i <= n; ++i){
		visited[i] = -1;
	}
	for(int i = 1; i <=n; ++i){
		if(visited[i] == -1){
			dfs_list_graph(lg, i, visited, v, &num);
		}
	}
    for (int i = num; i >= 1; i--){   
        fprintf(out1,"%d ",v[i]);
    }
    return 0;
}