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

typedef struct nod {
    int inf;
    struct nod *next;
}TNOD;

int ins_c(TNOD **prim, TNOD **ultim, int info)
{
    TNOD *p;
    int ok = 1;

    if (p = (TNOD*)malloc(sizeof(TNOD)))
    {
        p->inf = info;
        p->next = NULL;

        if (*prim == NULL)
            *prim = p;
        else
            (*ultim)->next = p;
        *ultim = p;
    }
    else
        ok = 0;

    return ok;
}

int extrage_c(TNOD **prim, TNOD **ultim, int *info)
{
    TNOD *p;
    int ok = 1;
    if (*prim)
    {
        p = *prim;
        *info = (*prim)->inf;
        (*prim) = (*prim)->next;
        free(p);
        if (*prim == NULL)
            *ultim = NULL;
    }
    else
        ok = 0;

    return ok;
}

int **matrice_adiacenta(char *numef, int *nrv, int *nrm)
{
    int **a,i,j,k;
    FILE *f;
    fopen_s(&f, numef, "r");

    fscanf_s(f, "%d %d", nrv, nrm);

    a = (int**)malloc(*nrv * sizeof(int*));

    for (i = 0; i < *nrv; i++)
        a[i] = (int*)malloc(*nrv * sizeof(int));

    for (i = 0; i < *nrv; i++)
        for (j = 0; j < *nrv; j++)
            a[i][j] = 0;

    for (k = 0; k < *nrm; k++)
    {
        fscanf_s(f, "%d %d", &i, &j);
        a[i - 1][j - 1] = 1;
        a[j - 1][i - 1] = 1;
    }

    fclose(f);

    return a;
}

void BF(int vi, int **a, int n, int **rez, int *nr)
{
    int i, j, *c, ok;
    TNOD *p, *u;
    p = u = NULL;

    c = (int*)malloc(n * sizeof(int*));
    *rez = (int*)malloc(n * sizeof(int));

    for (i = 0; i < n; i++)
        c[i] = 0;

    ok = ins_c(&p, &u, vi - 1);
    c[vi - 1] = 1;

    *nr = 0;

    while (p)
    {
        ok = extrage_c(&p, &u, &i);
        (*rez)[*nr] = i + 1;
        (*nr)++;
        for(j=0;j<n;j++)
            if (a[i][j] == 1 && c[j] == 0)
            {
                ok = ins_c(&p, &u, j);
                c[j] = 1;
            }


    }
    free(c);

}

int main()
{
    int i, **a, vi, *parc, cite,n,m;

    a = matrice_adiacenta("graf.txt", &n, &m);

    BF(1, a, n, &parc, &cite);

    for (i = 0; i < cite; i++)
        printf("%d ", parc[i]);

    free(parc);

    _getch();

    return 0;

}