#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifndef NODE
#define NODE
typedef struct Node
{
int value;
struct Node *next;
} Node;
#endif
typedef struct Queue
{
int size;
Node *front;
Node *rear;
} Queue;
typedef struct list_node {
// Nodul cu care are muchie detinatorul listei
int node;
struct list_node *next;
} list_node;
typedef struct graph {
// Numarul de noduri ale grafului
int no_nodes;
// Vector de pointer la capul listelor inlantuite de dimensiune <no_nodes>
// adj_heads[i] -> lista de adiacenta a nodului i
list_node **adj_heads;
} graph;
graph* create_graph(int no_nodes)
{
graph *gl = (graph *) malloc(sizeof(graph));
gl->no_nodes = no_nodes;
gl->adj_heads = (list_node **) calloc(no_nodes, sizeof(list_node *));
return gl;
}
// Adauga muchia (`v1`, `v2`) in graful `gm`
void insert_edge(graph *gl, int v1, int v2)
{
list_node *it, *new;
int found = 0;
for (it = gl->adj_heads[v1]; it != NULL; it = it->next)
if (it->node == v2) {
found = 1;
break;
}
if (found == 1)
return;
new = (list_node *) malloc(sizeof(list_node));
new->node = v2;
new->next = gl->adj_heads[v1];
gl->adj_heads[v1] = new;
}
static void delete_elem_list(list_node **list, int elem) {
list_node *toDelete, *prev;
if ((*list)->node == elem) {
toDelete = *list;
*list = (*list)->next;
free(toDelete);
return;
}
for (toDelete = (*list)->next, prev = *list;
toDelete != NULL && toDelete->node != elem;
toDelete = toDelete->next, prev = prev->next);
// No element to remove
if (toDelete == NULL)
return;
prev->next = toDelete->next;
free(toDelete);
}
// Sterge muchia (`v1`, `v2`) (daca exista) in graful `gm`
void remove_edge(graph *gl, int v1, int v2)
{
delete_elem_list(&gl->adj_heads[v1], v2);
}
static void free_list(list_node *list) {
list_node *it = list, *prev;
while (it != NULL) {
prev = it;
it = it->next;
free(prev);
}
}
// Distruge graful cu matrice de adiacenta `gm`
void destroy_graph(graph *gl)
{
int i;
for (i = 0; i < gl->no_nodes; i++)
free_list(gl->adj_heads[i]);
free(gl->adj_heads);
free(gl);
}
void init_queue(Queue **q)
{
*q = (Queue *) malloc(sizeof(Queue));
(*q)->front = (*q)->rear = NULL;
(*q)->size = 0;
}
int is_empty_queue(Queue *q)
{
return q->front == NULL ? 1 : 0;
}
void enqueue(Queue *q, int x)
{
Node *new = (Node *) malloc(sizeof(Node));
new->value = x;
new->next = NULL;
if (is_empty_queue(q)) {
q->front = q->rear = new;
q->size = 1;
return;
}
q->rear->next = new;
q->rear = new;
q->size++;
}
int size_queue(Queue *q)
{
return q->size;
}
void dequeue(Queue *q)
{
if (is_empty_queue(q) == 1)
return;
Node *del = q->front;
q->front = q->front->next;
free(del);
q->size--;
if (q->front == NULL)
q->rear = NULL;
}
int front(Queue *q)
{
return q->front->value;
}
void print_queue(Queue *q)
{
Node *it;
for (it = q->front; it != NULL; it = it->next) {
printf("%d ", it->value);
}
printf("\n");
}
void BFS(graph *gl, int starting_node, int *viz)
{
Queue *q;
init_queue(&q);
list_node *it;
viz[starting_node] = 1;
enqueue(q, starting_node);
while(!is_empty_queue(q)) {
starting_node = front(q);
dequeue(q);
for (it = gl->adj_heads[starting_node]; it != NULL; it = it->next)
if (viz[it->node] == 0) {
enqueue(q, it->node);
viz[it->node] = viz[starting_node] + 1;
}
}
free(q);
}
int main()
{
FILE *src;
FILE *dest;
src = fopen("bfs.in", "r");
dest = fopen("bfs.out", "w");
int N, M, S;
int *viz;
fscanf(src, "%d %d %d", &N, &M, &S);
graph *gl = create_graph(N);
viz = (int *) calloc(gl->no_nodes, sizeof(int));
int u, v;
// while (fscanf(src, "%d %d", &u, &v) != EOF)
// {
// insert_edge(gl, u-1, v-1);
// }
int i;
for (i = 0; i < M; i++) {
fscanf(src, "%d %d", &u, &v);
insert_edge(gl, u-1, v-1);
}
BFS(gl, S-1, viz);
for (i = 0; i < N; i++) {
fprintf(dest, "%d ", viz[i] - 1);
}
destroy_graph(gl);
free(viz);
fclose(src);
fclose(dest);
return 0;
}