Pagini recente » Cod sursa (job #2777332) | Cod sursa (job #1062689) | Cod sursa (job #2377921) | Cod sursa (job #1173714) | Cod sursa (job #2595106)
#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;
}