Pagini recente » Cod sursa (job #2702535) | Cod sursa (job #1628161) | Cod sursa (job #813144) | Cod sursa (job #1869238) | Cod sursa (job #2595130)
#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;
}