Cod sursa(job #2225270)

Utilizator AraldaAralda Pacurar Aralda Data 26 iulie 2018 15:04:46
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.79 kb
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct node {

	int key;
	struct node* next;

}node;

int descoperit[50001];
node* adj[50001];
node* stack;

void enqueue(node** first, int key) {

	node* x = (node *)malloc(sizeof(node));
	if (x == NULL) {

		perror("malloc failed");
		exit(1);
	}

	x->key = key;
	x->next = NULL;

	if (*first == NULL) {

		*first = x;
	}
	else {

		node* p = *first;

		while (p->next != NULL) {

			p = p->next;
		}

		p->next = x;
	}
}

void push(node** first, int key) {

	node* x = (node *)malloc(sizeof(node));
	if (x == NULL) {

		perror("malloc failed");
		exit(1);
	}

	x->key = key;
	x->next = NULL;

	if (*first == NULL) {

		*first = x;
	}
	else {

		x->next = *first;
		*first = x;
	}
}

int pop(node** first) {

	if (*first == NULL) {

		return -1;
	}

	node* p = *first;
	int key = p->key;

	*first = (*first)->next;
	p->next == NULL;
	free(p);

	return key;
}

void DFS(int s) {

	descoperit[s] = 1;

	node* u = adj[s];

	while (u) {

		if (descoperit[u->key] == 0) {

			DFS(u->key);
		}

		u = u->next;
	}

	push(&stack, s);
}

int main() {

	FILE* ip;
	FILE* op;

	ip = fopen("sortaret.in", "r");
	if (ip == NULL) {

		perror("Error opening input file");
		return 1;
	}

	op = fopen("sortaret.out", "w");
	if (op == NULL) {

		perror("Error opening output file");
		return 1;
	}

	int n, m;

	fscanf(ip, "%d%d", &n, &m);

	for (int i = 0; i < m; i++) {

		int x, y;

		fscanf(ip, "%d%d", &x, &y);

		enqueue(&adj[x], y);
	}

	for (int i = 1; i <= n; i++) {

		if (descoperit[i] == 0) {

			DFS(i);
		}
	}

	while (stack) {

		fprintf(op, "%d ", pop(&stack));
	}

	fclose(ip);
	fclose(op);

	return 0;
}