#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#define MAX_NODES 101000
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 print_int_linkedlist(LinkedList *list) {
Node *curr;
if (list == NULL) {
return;
}
curr = list->head;
while (curr != NULL) {
printf("%d ", *((int*)curr->data));
curr = curr->next;
}
printf("\n");
}
void print_list_graph(ListGraph *lg) {
int i;
for(i = 0; i < lg->nodes; i++) {
printf("%d: ", i);
print_int_linkedlist(lg->neighbors[i]);
}
}
void bfs_list_graph(ListGraph *lg, int node, int *visited, int *parents, int *dist) {
int i, j, val, v[1000];
void *nod;
struct Node *curr;
dist[node] = 0;
i = 0;
Queue *q = malloc(sizeof(Queue));
init_q(q);
visited[node] = 1;
enqueue(q, &node);
while(is_empty_q(q)==0) {
nod = front(q);
val = *((int *)nod);
curr = (lg->neighbors[val])->head;
while(curr != NULL) {
j = *((int*)curr->data);
if(visited[j] == 0) {
visited[j] = 1;
parents[j] = val;
dist[j] = dist[val] + 1;
v[i] = j;
enqueue(q, &v[i]);
i++;
}
curr = curr->next;
}
visited[val] = 1;
dequeue(q);
}
purge_q(q);
free(q);
}
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];
int time;
FILE *fin,*fout;
fin = fopen("bfs.in","rt");
fout = fopen("bfs.out","wt");
ListGraph *lg = malloc(sizeof(ListGraph));
fscanf(fin,"%d %d %d", &nodes, &edges, &node);
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]);
}
//print_list_graph(lg);
for(i=0;i<MAX_NODES;i++){
dist[i]=0;
visited[i]=0;
}
// memset(dist, 0, sizeof(dist));
// memset(visited, 0, sizeof(visited));
parents[i] = -1; /*i = 0:(nodes - 1) */
bfs_list_graph(lg, node -1 , visited, parents,dist);
for(i=0;i<lg->nodes;i++) {
if(visited[i] == 0 && i != node) {
dist[i] = -1;
}
}
for (i = 0; i < nodes; i++)
{
fprintf(fout, "%d ", dist[i]);
}
clear_list_graph(lg);
free(lg);
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;
}
/*
* Functia intoarce numarul de noduri din lista al carei pointer este trimis ca parametru.
*/
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) {
int i;
graph->nodes = nodes;
graph->neighbors = malloc(nodes * sizeof(LinkedList *));
for(i = 0; i < nodes; i++) {
graph->neighbors[i] = malloc(sizeof(LinkedList));
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) {
struct Node *curr;
curr = (graph->neighbors[src])->head;
while( curr != NULL) {
if(*((int *)curr->data) == dest) {
return 1;
}
}
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);
}