//Leandro Teófilo - RA134064
//Teoria dos Grafos - MO405
//Pruf Code

#include <stdio.h>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef vector<int> VInt;
typedef vector<VInt> VVInt;
typedef vector<bool> VBool;


VVInt mat_adj,lista_adj;
VInt set_dgree,pruf_code;

//-------------------------------------------------------------------------------------------
/*Função que gera a lista de adjacencias, a partir da matriz de adjacencia*/
void gera_lista(VVInt mat,int nvert)
{
    lista_adj = VVInt(nvert, VInt());
    int m,n;
    for(m=0;m<nvert;m++)
    {
        for(n=0;n<nvert;n++)
        {
            if(mat_adj[m][n]==1)
                lista_adj[m].push_back(n);
        }
    }

}
//-------------------------------------------------------------------------------------------
/*Função que imprime a lista de adjacencias*/
void print_ladj(VVInt mat,int nvert){
    int cont,m;
    for(m=0;m<nvert;m++)
    {
        if(mat[m].size()>0)
        {
            printf("%d: ",m+1);
            for(cont=0;cont<mat[m].size();cont++)
                printf("%d  ",mat[m][cont]+1);
            printf("\n\n");
        }

    }
}
//-------------------------------------------------------------------
/*Função que imprime a o Prüf Code*/
void print_code(VInt mat){
    VInt::iterator it;
    printf("PRUF CODE:\n\n\n");
    for(it=mat.begin();it!=mat.end();it++)
        printf("%d  ",*it+1);
    printf("\n\n\n");
}

//----------------------------------------------------------------------------------
/*Função que imprime a matriz de adjacencia*/
void print_madj(VVInt mat,int nvert){
    int m,j;
    for(m=0;m<nvert;m++)
    {
        for(j=0;j<nvert;j++)
                printf("%d  ",mat[m][j]);
        printf("\n\n\n");
    }
}

//-------------------------------------------------------------------
/*Função que imprime a o conjunto de graus dos vértices*/
void print_Dgree(VInt mat){
    VInt::iterator it;
    printf("CONJUNTO DE GRAUS DOS VERTICES\n\n\n");
      for(it=mat.begin();it!=mat.end();it++)
        printf("%d  ",*it);
    printf("\n\n\n");

}
//-----------------------------------------------------------------------------------------------


void le_arvore(int num_ver){

    mat_adj = VVInt(num_ver, VInt(num_ver,0)); //A matriz de adjac. e inicializada com tamanho num_ver X num_ver e com valor zero
    lista_adj= VVInt(num_ver, VInt());        //A matriz de incid. e inicializada em uma dim. c/ tamanho num_ver,a outra dim. vai depender do num. de vizinhos
    set_dgree=VInt(num_ver);    //Vetor que armazena a lista de graus, inicializado com tamanho num_ver
    int u,v,x;

    for(x=0;x<num_ver-1;x++){
        printf("\n");
        do
        {
            printf("\nAresta %d - V1: ",x+1);
            scanf("%d",&u);

        }while(u<1 || u>num_ver);

        do
        {
            printf("\nAresta %d - V2: ",x+1);
            scanf("%d",&v);

        }while(v<1 || v>num_ver || v==u);


        mat_adj[u-1][v-1]=mat_adj[v-1][u-1]=1; //Vai inserindo 1 nas posicoes onde os vertices sao adjacentes
        set_dgree[u-1]++; //Incrementa o grau do vertice u
        set_dgree[v-1]++; //Incrementa o grau do vertice v
    }


}
//-----------------------------------------------------------------------------------------------

int main(){

    int cont,nver,vizinho,m;
    VInt::iterator it,it2;

    while(1)
    {
        int num_arestas;
        VInt pruf_code=VInt();
        printf("\nDigite o numero de vertices da arvore: ");
        scanf("%d", &nver);
        le_arvore(nver);//Chama a funcao para gerar o grafo com a arvore, criando assim a matriz de adjacencias
        gera_lista(mat_adj,nver);//Gera a mat. de incidencias a partir da matriz de adjacencias
//--------------------------------------------------------------------------------------------------------
        printf("\n\n\nLista de ADJACENCIAS (Antes da geracao do Pruf Code)\n\n");
        print_ladj(lista_adj,nver);//Imprimindo a lista de ADJACENCIAS da arvore inicial
        printf("\nMatriz de ADJACENCIAS (Antes da geracao do Pruf Code)\n\n");
        print_madj(mat_adj,nver);    //Imprimindo MATRIZ DE ADJACENCIAS inicial


//----------------------------------------------------------------

        for(cont=0;cont<nver-2;) //cont armazenara o numero de vertices ja incluidos no Pruf Code
        {
            for(m=0;m<nver-1;m++) //A busca pelas folhas de menor valor se dará através da lista de graus
            {
                if(set_dgree[m]==1 && cont<nver-2) //Verifica se o vertice eh uma folha e verifica se Pruf Code ainda não está completo
                {
                    it2=set_dgree.begin();
                    for(it=mat_adj[m].begin();it!=mat_adj[m].end();it++) //Faz a busca pelo vizinho da folha
                    {
                        if(*it==1 && *it2>1)
                              vizinho=it2-set_dgree.begin();
                        else
                            it2++;
                    }
                    pruf_code.push_back(vizinho); //Adiciona o vizinho da folha de menor valor ao Pruf Code
                    mat_adj[m][vizinho]=0;
                    mat_adj[vizinho][m]=0;
                    set_dgree[vizinho]--;         //Diminui o grau do vizinho
                    set_dgree[m]--;               //Diminui o grau da folha
                    m=0;                          /*Reinicializa m c/valor inicial, para que novamente a busca se inicie a partir do vertice
                                                de menor valor, pois agora podem ter surgido novas folhas*/
                    cont++;                       //Incrementa cont, para o controle do total de itens no Pruf Code
                }
            }

        }
        gera_lista(mat_adj,nver); //Gera a nova Lista de Adjacencias, com base na Matriz de adjacencias atualizada.
//-----------------------------------------------------------------------------------------------------------------------------------
        printf("\nLista de ADJACENCIAS (Depois da geracao do Pruf Code)\n\n");
        print_ladj(lista_adj,nver);//Imprimindo a matriz de incidencia da arvore
        printf("\nMatriz de ADJACENCIAS (Depois da geracao do Pruf Code)\n\n");
        print_madj(mat_adj,nver);    //Imprimindo MATRIZ DE ADJACENCIAS
        print_code(pruf_code);      //Imprimindo o Pruf Code
        printf("\n\n");

//--------------------------------------------------------

    }
}