#define NRMAXNODURI 64
#include <stdio.h>

typedef struct
{
int nrNoduri;
char tabChei[NRMAXNODURI];
int tabVizitat[NRMAXNODURI];
char matAdiacenta[NRMAXNODURI][NRMAXNODURI];
}Graf;

typedef struct
{
    int nrElemente;
    int tabElemente[NRMAXNODURI];
} Coada;

void initializare(Graf &g)
{
    int i,j;
    g.nrNoduri=0;
    for (i=0;i<NRMAXNODURI;i++)
    {
        g.tabChei[i]=0;
        g.tabVizitat[i]=0;
    }
    for (i=0;i<NRMAXNODURI;i++)
    {
        for(j=0;j<NRMAXNODURI;j++)
        {
            g.matAdiacenta[i][j]=0;
        }
    }
}

void reinitializare(Graf &g)
{
    int i;
    for (i=0;i<NRMAXNODURI;i++)
    {
        g.tabVizitat[i]=0;
    }
}

void afisare(Graf g)
{
    int i,j;
    printf("\nLista de chei;\n");
    for (i=0;i<g.nrNoduri;i++)
    {
        printf("%c ",g.tabChei[i]);
    }
printf("\nMatricea de adiacenta:\n");
for (i=0;i<g.nrNoduri;i++)
{
    for(j=0;j<g.nrNoduri;j++)
    {
        printf("%d ",g.matAdiacenta[i][j]);
    }
    printf("\n");
}
}
void adaugaNod(Graf &g,char cheie)
{
    g.tabChei[g.nrNoduri]=cheie;
    g.nrNoduri++;
}
void adaugaArc(Graf &g,int index1,int index2)
{
    g.matAdiacenta[index1][index2]=1;
    g.matAdiacenta[index2][index1]=1;
}

void stergereArc(Graf &g,int index1,int index2)
{
   g.matAdiacenta[index1][index2]=0;
 g.matAdiacenta[index2][index1]=0;
}
void traverseazaInAdancime2(Graf &g,int indexNod)
{
    int i;
    if (!g.tabVizitat[indexNod])
        {
printf("%c ",g.tabChei[indexNod]);
    g.tabVizitat[indexNod]=1;
    for (i=0;i<g.nrNoduri;i++)
    {
        if (g.matAdiacenta[indexNod][i])
        {
            traverseazaInAdancime2(g,i);
        }
    }
}
}

void traverseazaInAdancime(Graf g)
{

    int i;
    printf("\nTraversare in adancime:\n");
    for (i=0;i<g.nrNoduri;i++)
    {
        if (g.tabVizitat[i]==0)
        {

            traverseazaInAdancime2(g,i);
            printf("\n");

        }
    }
    printf("\n");
}

void initializare(Coada &coada)
{
    int i;
    for (i=0;i<NRMAXNODURI;i++)
    {
        coada.tabElemente[i]=-1;
    }
    coada.nrElemente=0;
}

void adauga(Coada &coada,int indexNod)
{
    //printf("Adauga %d\n", indexNod);
    coada.tabElemente[coada.nrElemente++]=indexNod;
}
int scoate(Coada &coada)
{
 int i;
    int indexNod=coada.tabElemente[0];
    for (i=0;i<coada.nrElemente;i++)
    {
        coada.tabElemente[i]=coada.tabElemente[i+1];
    }
    coada.nrElemente--;
    //printf("Scoatem %d\n", indexNod);
    return indexNod;
}

int vida(Coada coada)
{
    return coada.nrElemente==0;

}

void traverseazaPrinCuprindere2(Graf &g, int indexNod)
{
    int i;
    Coada coada;
    initializare(coada);

    adauga(coada,indexNod);
    g.tabVizitat[indexNod]=1;
    do
    {
        indexNod=scoate(coada);
        printf("%c ",g.tabChei[indexNod]);
        for (i=0;i<g.nrNoduri;i++)
        {
            if (g.matAdiacenta[indexNod][i] && !(g.tabVizitat[i]))
            {
                g.tabVizitat[i]=1;
                adauga(coada,i);
            }
        }
    }
    while (!vida(coada));
}

void traverseazaPrinCuprindere(Graf g)
{
    int i;
    printf("\nTraversare prind cuprindere:\n");
    for (i=0;i<g.nrNoduri;i++)
    {
        if (g.tabVizitat[i]==0)
        {
            traverseazaPrinCuprindere2(g,i);
            printf("\n");
        }
    }
    printf("\n");
}

int main()
{
    Graf g;
    initializare(g);

    adaugaNod(g,'A');
    adaugaNod(g,'B');
    adaugaNod(g,'C');
    adaugaNod(g,'D');

    adaugaNod(g,'E');
    adaugaNod(g,'F');
    adaugaNod(g,'G');
    adaugaNod(g,'H');
    adaugaNod(g,'I');
    adaugaNod(g,'J');
    adaugaNod(g,'K');
    adaugaNod(g,'L');
    adaugaNod(g,'M');

    adaugaArc(g,0,1);
    adaugaArc(g,0,2);
    adaugaArc(g,0,3);
    adaugaArc(g,0,4);

    adaugaArc(g,1,2);
    adaugaArc(g,1,3);
    adaugaArc(g,2,3);
    adaugaArc(g,4,5);
    adaugaArc(g,5,6);
    adaugaArc(g,7,8);
    adaugaArc(g,9,10);
    adaugaArc(g,11,12);
    traverseazaInAdancime(g);

    reinitializare(g);
    traverseazaPrinCuprindere(g);
}