#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#define MAX_NODES 301000
typedef struct Node {
void *data;
struct
Node *next;
} Node;
typedef struct {
Node *head;
Node *tail;
int size;
} LinkedList;
void init_list(LinkedList *list);
void add_nth_node(LinkedList *list, int n, void *new_data);
Node* remove_nth_node(LinkedList *list, int n);
int get_size(LinkedList *list);
void free_list(LinkedList **list);
void print_int_linkedlist(LinkedList *list);
void print_string_linkedlist(LinkedList *list);
typedef struct {
LinkedList **neighbors;
int nodes;
} ListGraph;
void init_list_graph(ListGraph *graph, int nodes);
void add_edge_list_graph(ListGraph *graph, int src, int *dest);
int has_edge_list_graph(ListGraph *graph, int src, int dest);
LinkedList* get_neighbours_list_graph(ListGraph *graph, int node);
void remove_edge_list_graph(ListGraph *graph, int src, int dest);
void clear_list_graph(ListGraph *graph);
typedef struct {
LinkedList *list;
} Queue;
void init_q(Queue *q);
int get_size_q(Queue *q);
int is_empty_q(Queue *q);
void* front(Queue *q);
void dequeue(Queue *q);
void enqueue(Queue *q, void *new_data);
void clear_q(Queue *q);
void purge_q(Queue *q);
void dfs_list_graph(ListGraph *lg, int node, int *visited, int *t_desc, int *t_fin, int *time) {
struct Node *curr;
int i;
curr = lg->neighbors[node]->head;
visited[node] = 1;
t_desc[node] = (*time)++;
while(curr!=NULL) {
i = *((int*)curr->data);
if(visited[i] == 0) {
dfs_list_graph(lg,i,visited,t_desc,t_fin,time);
}
curr = curr->next;
}
t_fin[node] = (*time)++;
}
void print_times(int* visited, int* t_fin, int nodes, FILE *fout)
{
int i;
for (i = nodes -1; i >=0; i--)
{
visited[i]=i+1;
fprintf(fout,"%d ",visited[i]);
}
}
int main(void) {
int nodes, edges, node, i;
int x[MAX_NODES], y[MAX_NODES];
int visited[MAX_NODES];
int parents[MAX_NODES], dist[MAX_NODES],t_desc[MAX_NODES],t_fin[MAX_NODES];
int time;
FILE *fin,*fout;
fin = fopen("sortaret","rt");
if(fin==NULL) {
printf("NU se poate deschide fisierul");
return 0;
}
fout = fopen("sortaret.out","wt");
if(fout==NULL) {
printf("NU se poate deschide fisierul");
return 0;
}
ListGraph *lg = malloc(sizeof(ListGraph));
fscanf(fin,"%d %d", &nodes, &edges);
init_list_graph(lg, nodes);
for (int i = 0; i < edges; ++i) {
fscanf(fin,"%d %d", &x[i], &y[i]);
x[i]=x[i]-1;
y[i]=y[i]-1;
add_edge_list_graph(lg, x[i], &y[i]);
}
for(i=0;i<=nodes;i++){
dist[i]=0;
visited[i]=0;
t_fin[i] = 0;
t_desc[i] = 0;
}
time = 0;
int nr,aux,j;
nr = 0;
for(i=0;i< nodes; i++) {
if(visited[i]==0) {
time = 0;
dfs_list_graph(lg, i, visited, t_desc, t_fin, &time);
nr++;
}
}
for(i=0;i<nodes;i++) {
visited[i] = i;
}
for(i=0;i<nodes-1;i++) {
for(j=i+1;j<nodes;j++) {
if(t_fin[i] > t_fin[j]) {
aux = t_fin[i];
t_fin[i] = t_fin[j];
t_fin[j] = aux;
aux = visited[i];
visited[i] = visited[j];
visited[j] = aux;
}
}
}
print_times(visited, t_fin, lg->nodes,fout);
clear_list_graph(lg);
free(lg);
fclose(fin);
fclose(fout);
return 0;
}
void init_list(LinkedList *list) {
list->head = NULL;
list->tail = NULL;
list->size = 0;
}
void add_nth_node(LinkedList *list, int n, void *new_data) {
Node *prev, *curr;
Node *new_node;
if (list == NULL) {
return;
}
if (n > list->size) {
n = list->size;
} else if (n < 0) {
return;
}
curr = list->head;
prev = NULL;
while (n > 0) {
prev = curr;
curr = curr->next;
--n;
}
new_node = malloc(sizeof(Node));
if (new_node == NULL) {
perror("Not enough memory to add element!");
exit(-1);
}
new_node->data = new_data;
new_node->next = curr;
if (prev == NULL) {
/* Adica n == 0. */
list->head = new_node;
} else {
prev->next = new_node;
}
if (new_node->next == NULL) {
list->tail = new_node;
}
list->size++;
}
Node* remove_nth_node(LinkedList *list, int n) {
Node *prev, *curr;
if (list == NULL) {
return NULL;
}
if (list->head == NULL) { /* Lista este goala. */
return NULL;
}
if (n > list->size - 1) {
n = list->size - 1;
} else if (n < 0) {
return NULL;
}
curr = list->head;
prev = NULL;
while (n > 0) {
prev = curr;
curr = curr->next;
--n;
}
if (prev == NULL) {
/* Adica n == 0. */
list->head = curr->next;
} else {
prev->next = curr->next;
if (prev->next == NULL) {
list->tail = prev;
}
}
list->size--;
return curr;
}
int get_size(LinkedList *list) {
if (list == NULL) {
return -1;
}
return list->size;
}
void free_list(LinkedList **pp_list) {
struct Node *currNode;
if (pp_list == NULL || *pp_list == NULL) {
return;
}
while(get_size(*pp_list) > 0) {
currNode = remove_nth_node(*pp_list, 0);
free(currNode);
}
free(*pp_list);
*pp_list = NULL;
}
void init_list_graph(ListGraph *graph, int nodes) {
graph->nodes = nodes;
graph->neighbors = malloc(nodes * sizeof(LinkedList));
if (graph->neighbors == NULL) {
perror("Not enough memory to initialize the adjacency list!");
exit(-1);
}
for (int i = 0; i < nodes; ++i) {
graph->neighbors[i] = malloc(sizeof(LinkedList));
if (graph->neighbors[i] == NULL) {
perror("Not enough memory to initialize the adjacency list!");
exit(-1);
}
init_list(graph->neighbors[i]);
}
}
void add_edge_list_graph(ListGraph *graph, int src, int *dest) {
add_nth_node(graph->neighbors[src] , 0x7fffffff, dest);
}
int has_edge_list_graph(ListGraph *graph, int src, int dest) {
Node *head = graph->neighbors[src]->head;
int crt_node;
while (head != NULL) {
crt_node = *(int *)head->data;
if (crt_node == dest) {
return 1;
}
head = head->next;
}
return 0;
}
LinkedList* get_neighbours_list_graph(ListGraph *graph, int node) {
return graph->neighbors[node];
}
void remove_edge_list_graph(ListGraph *graph, int src, int dest) {
struct Node *curr;
int poz;
poz = 0;
curr=(graph->neighbors[src])->head;
while( curr!=NULL) {
if(*((int *)curr->data) == dest) {
remove_nth_node(graph->neighbors[src],poz);
}
poz++;
curr = curr->next;
}
}
void clear_list_graph(ListGraph *graph) {
int i;
for(i = 0; i < graph->nodes; i++) {
free_list(&graph->neighbors[i]);
}
free(graph->neighbors);
}
void init_q(Queue *q) {
q->list = malloc(sizeof(LinkedList));
if (q == NULL) {
perror("Not enough memory to initialize the queue!");
exit(-1);
}
init_list(q->list);
}
int get_size_q(Queue *q) {
return q->list->size;
}
int is_empty_q(Queue *q) {
return get_size_q(q) == 0;
}
void* front(Queue *q) {
if (q == NULL || q->list == NULL) {
return NULL;
}
return q->list->head->data;
}
void dequeue(Queue *q) {
struct Node *node;
if (q == NULL || q->list == NULL) {
return;
}
node = remove_nth_node(q->list, 0);
free(node);
}
void enqueue(Queue *q, void *new_data) {
add_nth_node(q->list, q->list->size, new_data);
}
void clear_q(Queue *q) {
struct Node *node;
while (!is_empty_q(q)) {
node = remove_nth_node(q->list, 0);
free(node);
}
}
void purge_q(Queue *q) {
clear_q(q);
free(q->list);
}