BFS

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

typedef struct Node{
    int n;
    struct Node *next;
} node;

typedef struct Queue{
    node *first;
    node *last;
} queue;

int n;


node *init_node(int n){
    node *tmp = malloc(sizeof(node));
    tmp->n = n;
    tmp->next = NULL;
    return tmp;
}

//Queue:

queue *init_queue(){
    queue *q = malloc(sizeof(queue));
    q->first = q->last = NULL;
    return q;
}

int is_queue_empty(queue *q){
    return (q->first == NULL);
}

node *pop(queue *q){
    if (is_queue_empty(q))
        return NULL;
    node *tmp = q->first;
    q->first = q->first->next;

    if (tmp == q->last)
        q->last = NULL;

    return tmp;
}

void push_back(queue *q, node *el){
    if (is_queue_empty(q)){
        q->first = q->last = el;
    } else {
        q->last->next = el;
        q->last = el;
    }
}

void free_queue(queue *q){
    if (is_queue_empty(q)){
        free(q);
        return;
    }
    node *tmp2;
    node *tmp;

    tmp = q->first;
    if (tmp->next == NULL){
        free(tmp);
    } else {
         tmp2 = tmp->next;
        while (tmp2!= NULL){
            free(tmp);
            tmp = tmp2;
            tmp2 = tmp2->next;
        }
        free(tmp);
    }
    free(q);
}

//Main part:

int BFS(queue *q, char *visited, char *queued, int **G, int target_node) {
    if (is_queue_empty(q)) return 0;
    node *tmp = pop(q);

    visited[tmp->n] = 1;
    if (tmp->n == target_node)
        return 1;

    for (int i = 0; i < n; i++)
        if (G[tmp->n][i] && !queued[i] && !visited[i]) {
            push_back(q, init_node(i));
            queued[i] = 1;
        }
    return BFS(q, visited, queued, G, target_node);
}



int main(){
    int   **G;
    FILE *fin;

    fin = fopen("input.txt", "r");
    if (!fin){
        //handle this situation
        exit(EXIT_FAILURE);
    }

    fscanf(fin, "%d", &n);
    G = (int **) malloc(sizeof(int *) * n);
    for (int i = 0; i < n; i++)
        G[i] = (int *) calloc(n, sizeof(int));

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            fscanf(fin, "%d", &G[i][j]);

    //Entering set of vertexes to start BFS:
    int tmp;
    int target_node;
    int is_reachable;

    char *queued = calloc(n, sizeof(int));
    char *visited = calloc(n, sizeof(int));

    char ch;
    queue *q = init_queue();

    while (fscanf(fin, "%d%c", &tmp, &ch) == 2) {
        push_back(q, init_node(tmp - 1));
        queued[tmp - 1] = 1;
        if (ch == '\n')
            break;
    }
    fscanf(fin, "%d", &target_node);
    target_node--;

    is_reachable = BFS(q, visited, queued, G, target_node);
    free_queue(q);
    printf(is_reachable ? "YES" : "NO");

    getch();
    return 0;
}