Cod sursa(job #2595106)

Utilizator razvan.ursatanuUrsatanu Razvan razvan.ursatanu Data 7 aprilie 2020 02:04:48
Problema Sortare topologica Scor 90
Compilator c-64 Status done
Runda laborator_7_sd_313cab Marime 3.53 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;

typedef struct {
    LinkedList *list;
}Stack;

void init_stack(Stack *stack) {
    stack->list = malloc(sizeof(LinkedList));
    stack->list->head = NULL;
    stack->list->tail = NULL;
    stack->list->size = 0;
}

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 pop_stack(Stack *stack) {
    if(stack->list == NULL) {
        return;
    }
    struct Node *p;
    p = stack->list->head->next;
    free(stack->list->head);
    stack->list->head = p;
    stack->list->size--;
}

void push_stack(Stack *stack, void *new_data) {
    if(stack->list == NULL){
        return;
    }
    struct Node *p;
    p = malloc(sizeof(struct Node));
    p->data = new_data;
    p->next = stack->list->head;
    stack->list->head = p;
    stack->list->size++;
}

void* peek_stack(Stack *stack) {
    return stack->list->head->data;
}

int is_empty_stack(Stack *stack) {
    if(stack->list->size == 0) {
        return 1;
    }
    return 0;
}


void dfs_list_graph(ListGraph *lg, int node, int *visited, Stack *st, 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, st, num);
        }
        p = p->next;
    }
    push_stack(st, &num[node]);
}

void print_list_graph(ListGraph *lg) {
    for(int i = 1; i <= lg->nodes; ++i){
        struct Node *p;
        p = lg->neighbors[i]->head;
        printf("%d", i);
        printf(": ");
        while(p != NULL){
                printf("%d ", *(int*)p->data);
                p = p->next;
        }
        printf("\n");
    }
}

int main() {
	int n, m, x[NMAX], y[NMAX], visited[NMAX];
	ListGraph *lg;
	lg = malloc(sizeof(ListGraph));

	Stack *st;
	st = malloc(sizeof(Stack));
	init_stack(st);
	FILE *in1 = fopen("sortaret.in", "rt");
	FILE *out1 = fopen("sortaret.out", "wt");
	fscanf(in1, "%d%d", &n, &m);
	init_list_graph(lg, n);
	int *num = malloc(n * sizeof(int));
    for(int i = 0; i <= n; ++i) {
        num[i] = i;
    }

	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, st, num);
		}
	}
	while (!is_empty_stack(st)) {
        fprintf(out1, "%d ", *(int *)peek_stack(st));
        pop_stack(st);
    }
    fclose(in1);
    fclose(out1);
    return 0;
}