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

typedef struct Node
{
    int data;
    struct Node *next;
} Node;

void adding_to_queue(int peak, Node *queue)
{
    if(queue == NULL){
        queue = (Node*)malloc(sizeof(Node));
        queue->data = peak;
        queue->next = NULL;
    } else {
        Node *cur = queue;
        while(cur->next != NULL){
            cur = cur->next;
        }
        cur->next = (Node*)malloc(sizeof(Node));
        cur->next->data = peak;
        cur->next->next = NULL;
    }
}

int delete_from_queue(Node *queue)
{
    int peak = queue->data;
    if(queue->next != NULL) queue = queue->next;
    else queue = NULL;

    return peak;
}

int is_full(int *numbers_of_peaks, int amount_of_peaks)
{
    int i = 0, result = -1;
    for(i = 0; i < amount_of_peaks; ++i)
    {
        if(numbers_of_peaks[i] != 2) result = 1;
    }
    if(result == -1) result = 0;

    return result;
}

int **adjancency_matrix_creating(int amount_of_peaks)
{
    int i = 0, j = 0;

    int **adjacency_matrix;
    adjacency_matrix = (int**)malloc(amount_of_peaks * sizeof(int*));

    for (i = 0; i < amount_of_peaks; i++)
    {
        adjacency_matrix[i] = (int*)malloc(amount_of_peaks * sizeof(int));
    }

    //заполняем матрицу смежности
    for(i = 0; i < amount_of_peaks; ++i)
    {
        printf("С какими вершинами смежна %d вершина? После введите 0n", i+1);

        int is_scanf = -1, peak = -1;
    //заполняем смежные вершины
        while(peak)
        {
            is_scanf = scanf("%d", &peak);

            if(is_scanf)
            {
                adjacency_matrix[i][peak-1] = 1;
            }
        }
    //заполняем остальное
        for(j = 0; j < amount_of_peaks; ++j)
        {
            if(adjacency_matrix[i][j] != 1)
            {
                adjacency_matrix[i][j] = 0;
            }
        }
    }
    //вывод матрицы смежности
    printf("nМатрица смежности:n");

    for(i = 0; i < amount_of_peaks; ++i)
    {
        for(j = 0; j < amount_of_peaks; ++j)
        {
            printf("%d ", adjacency_matrix[i][j]);
        }
        printf("n");
    }

    return adjacency_matrix;
}

int main()
{
    //Запрашиваем количество вершин и матрицу смежности
    system("chcp 1251");

    int amount_of_peaks = 0, i = 0, j = 0;

    printf("Сколько вершин в графе? ");
    scanf("%d", &amount_of_peaks);

    int **adjacency_matrix = adjancency_matrix_creating(amount_of_peaks);

    //обход
    Node *queue = NULL;

    int peak_start;
    int *numbers_of_peaks = (int*)malloc(amount_of_peaks * sizeof(int));

    for(i = 0; i < amount_of_peaks; ++i)
    {
        numbers_of_peaks[i] = 0;
    }

    printf("С какой вершины начать обход? ");
    scanf("%d", &peak_start);

    peak_start = peak_start-1;

    adding_to_queue(peak_start, queue);

    numbers_of_peaks[peak_start] = 1;

    int current_peak, checking = -1;

    do
    {
        current_peak = delete_from_queue(queue);

        if(numbers_of_peaks[current_peak] == 1)
        {
            for(i = 0; i < amount_of_peaks; ++i)
            {
                if(adjacency_matrix[current_peak][i] == 1)
                {
                    if(numbers_of_peaks[i] == 0)
                    {
                        adding_to_queue(i, queue);
                        numbers_of_peaks[i] = 1;
                    }
                }
            }
            numbers_of_peaks[current_peak] = 2;
            printf("Обработанная вершина: %dn", current_peak);

            checking = is_full(numbers_of_peaks, amount_of_peaks);
        }
    } while(checking);

    for(i = amount_of_peaks-1; i >= 0; i--)
    {
        free(adjacency_matrix[i]);
    }

    free(adjacency_matrix);

    return 0;
}