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


typedef struct vertice {
    int grau;
    list<int> AdjL;

    string cor;
    int dist;
    int pai;
    int tempo;
} 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
// ---------------------------------------
int digraph_create(digraph& G);
void digraph_delete(digraph& G);


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

    digraph G;
    if (!digraph_create(G)) {cout<<"Arquivo inexistente\n"; return -1;}

    // Busca em Largura
    busca_larg(G, 0);
    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;
    }

    // Busca em Profundidade (original, recursiva)
    busca_prof(G, 0);
    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;
    }

    // Busca em Profundidade (com pilha)
    busca_prof2(G, 0);
    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;
    }

    digraph_delete(G);
    return 0;
}


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

// ---------------------------------
// Busca em largura
// ---------------------------------
void busca_larg(digraph& G, int s) {
    list<int>::iterator it;
    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();  Fila.pop();
        G.V[u].tempo = ++tempo;
        for (it=G.V[u].AdjL.begin(); it!=G.V[u].AdjL.end(); ++it) {
            int v = (*it);
            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)
// --------------------------------------------
int tempo; // variavel global

void busca_prof_rec(digraph& G, int u) {
    list<int>::iterator it;
    G.V[u].cor = "cinza";
    G.V[u].tempo = ++tempo;
    for (it=G.V[u].AdjL.begin(); it!=G.V[u].AdjL.end(); ++it) {
        int v = (*it);
        if (G.V[v].cor=="branco") {
            G.V[v].pai = u;
            busca_prof_rec(G,v);
        }
    }
    G.V[u].cor = "preto";
}

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;
    }
    tempo = 0;
    busca_prof_rec(G,s);
}

// ---------------------------------------
// Busca em profundidade (com pilha)
// ---------------------------------------
void busca_prof2(digraph& G, int s) {
    list<int>::reverse_iterator it;
    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 (it=G.V[u].AdjL.rbegin(); it!=G.V[u].AdjL.rend(); ++it) {
            int v = (*it);
            if (G.V[v].cor == "branco") {
                G.V[v].pai = u;
                Pilha.push(v);
            }
        }
        G.V[u].cor = "preto";
    }
}

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


// ------------------------------------
// ------------------------------------
int digraph_create(digraph& G) {
    ifstream arq;
    arq.open("entrada_busca_adjL.txt");
    if (arq.fail()) return 0;
    arq >> G.N;
    G.M=0; G.V = NULL;
    G.V = new vertice[G.N];

    for (int x=0; x<G.N; x++) {
        int grau;
        arq >> grau;
        G.V[x].grau = grau;
        G.M += grau;
        for (int k=0; k<grau; k++) {
            int y;
            arq >> y;
            G.V[x].AdjL.push_back(y);
        }
    }
    arq.close();
    return 1;
}
// ------------------------------------
// ------------------------------------
void digraph_delete(digraph& G) {
    delete[] G.V;
    G.V = NULL;
}