Pagini recente » Istoria paginii runda/a_a_a | Cod sursa (job #1761747) | Cod sursa (job #2220964) | Cod sursa (job #121940) | Cod sursa (job #2225271)
#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;
}