// ------------------------------------------------------------------------------------------------
// ---- BUSCA EM PROFUNDIDADE E EM LARGURA --------------------------------------------------------
// ------------------------------------------------------------------------------------------------
#include <iostream>
#include <fstream>
#include <cmath>
#include <ctime>
#include <climits>
#include <windows.h>
#include <stack>
#include <queue>
using namespace std;


typedef struct vertice {
    int grau;
    int* adjL;

    string cor;
    int dist;
    int pai;
    int tempo;
    int fim;
} vertice;

typedef struct digraph {
	int N;// numero de vertices
	int M;// numero de arestas
	vertice* V;
} digraph;


// ---------------------------------------
// Busca em Largura e em Profundidade
// ---------------------------------------
void busca_larg(digraph& G, int s);//busca largura
void busca_prof(digraph& G, int s);//busca prof  (original, recursiva)
void busca_prof2(digraph& G, int s);//busca prof2 (com pilha)


// ---------------------------------------
// Manutenção de grafos
// ---------------------------------------
void digraph_create(digraph& G, int tipo);
void digraph_delete(digraph& G);


// ------------------------------------------------------------------------------------------------
// ------ MAIN ------------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
int main() {
    int i,j,k;

    digraph G;
    digraph_create(G,2);// matriz de adj por arquivo

    // Busca em Largura
    busca_larg(G, 0);
    //ofstream arq;
    //arq.open("saida_busca_larg.txt");
    cout<<"\n-----------------------Busca em Largura --------------------------------\n";
    for (i=0; i<G.N; i++) {
        cout << "(vertice,distancia,pai,tempo)=(" << i << "," << G.V[i].dist << "," << G.V[i].pai << "," << G.V[i].tempo << ")" << endl;
    }
    //arq.close();

    // Busca em Profundidade (original, recursiva)
    busca_prof(G, 0);
    //arq.open("saida_busca_prof.txt");
    cout<<"\n-----------------------Busca em Profundidade (original, recursiva) -----\n";
    for (i=0; i<G.N; i++) {
        cout << "(vertice,pai,tempo)=(" << i << "," << G.V[i].pai << "," << G.V[i].tempo << ")" << endl;
    }
    //arq.close();

    // Busca em Profundidade (com pilha)
    busca_prof2(G, 0);
    //arq.open("saida_busca_prof2.txt");
    cout<<"\n-----------------------Busca em Profundidade (com pilha) ---------------\n";
    for (i=0; i<G.N; i++) {
        cout << "(vertice,pai,tempo)=(" << i << "," << G.V[i].pai << "," << G.V[i].tempo << ")" << endl;
    }
    //arq.close();

    digraph_delete(G);
    return 0;
}


// ------------------------------------------------------------------------------------------------
// ---- BUSCA EM PROFUNDIDADE E EM LARGURA --------------------------------------------------------
// ------------------------------------------------------------------------------------------------

// ---------------------------------
// Busca em largura
// ---------------------------------
void busca_larg(digraph& G, int s) {
    int tempo = 0;
    for (int i=0; i<G.N; i++) {
        G.V[i].cor = "branco";
        G.V[i].dist=INT_MAX;
        G.V[i].pai = -1;
        G.V[i].tempo=0;
    }
    G.V[s].cor = "cinza";
    G.V[s].dist = 0;
    queue<int> Fila;
    Fila.push(s);
    while (! Fila.empty()) {
        int u = Fila.front();
        G.V[u].tempo = tempo++;
        Fila.pop();
        for (int k=0; k<G.V[u].grau; k++) {
            int v = G.V[u].adjL[k];
            if (G.V[v].cor == "branco") {
                G.V[v].cor = "cinza";
                G.V[v].dist = G.V[u].dist + 1;
                G.V[v].pai = u;
                Fila.push(v);
            }
        }
        G.V[u].cor = "preto";
    }
}

// --------------------------------------------
// Busca em profundidade (original, recursiva)
// --------------------------------------------
void busca_prof_rec(digraph& G, int u, int& tempo) {
    G.V[u].cor = "cinza";
    G.V[u].tempo = tempo++;
    for (int k=0; k<G.V[u].grau; k++) {
        int v = G.V[u].adjL[k];
        if (G.V[v].cor!="branco") continue;
        G.V[v].pai = u;
        busca_prof_rec(G,v,tempo);
    }
    G.V[u].cor = "preto";
    G.V[u].fim = (--tempo)++;
}

void busca_prof(digraph& G, int s) {
    for (int i=0; i<G.N; i++) {
        G.V[i].cor = "branco";
        G.V[i].pai = -1;
        G.V[i].tempo=0;
    }
    int tempo = 0;
    busca_prof_rec(G,s,tempo);
}

// ---------------------------------------
// Busca em profundidade (com pilha)
// ---------------------------------------
void busca_prof2(digraph& G, int s) {
    int tempo = 0;
    for (int i=0; i<G.N; i++) {
        G.V[i].cor = "branco";
        G.V[i].pai = -1;
        G.V[i].tempo=0;
    }
    stack<int> Pilha;
    Pilha.push(s);
    while (! Pilha.empty()) {
        int u = Pilha.top();   Pilha.pop();
        if (G.V[u].cor!="branco") continue;
        G.V[u].cor = "cinza";
        G.V[u].tempo = tempo++;
        for (int k=G.V[u].grau-1; k>=0; k--) {
            int v = G.V[u].adjL[k];
            if (G.V[v].cor != "branco") continue;
            G.V[v].pai = u;
            Pilha.push(v);
        }
        G.V[u].cor = "preto";
    }
}

// ------------------------------------------------------------------------------------------------
// ---- MANUTENÇÃO DE GRAFOS ----------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------


// ------------------------------------
// ------------------------------------
void digraph_create(digraph& G, int tipo) {
    G.N=0; G.M=0;
    G.V = NULL;

    ifstream arq;
    arq.open("entrada_busca_adjL.txt");
    arq >> G.N;

    G.V = new vertice[G.N];
    for (int i=0; i<G.N; i++) {
        int grau;
        arq >> grau;
        G.V[i].grau = grau;
        G.M += grau;
        G.V[i].adjL = new int[grau];
        for (int k=0; k<grau; k++) {
            arq >> G.V[i].adjL[k];
        }
    }
}

// ------------------------------------
// ------------------------------------
void digraph_delete(digraph& G) {
    for (int i=0; i<G.N; i++) {
        if (G.V[i].adjL != NULL) delete[] G.V[i].adjL;
        G.V[i].adjL = NULL;
    }
    delete[] G.V;
    G.V = NULL;
}