// -----------------------------------------------------------------
// ---- CODIGOS DOS EXERCICIOS DA LISTA 2 --------------------------
// -----------------------------------------------------------------
#include <iostream>
#include <fstream>
#include <cmath>
#include <ctime>
#include <climits>
#include <cfloat>
#include <windows.h>
#include <stack>
using namespace std;


typedef struct vertice {
    int grau;
    int* adjL;

    int pai;
    int tempo;
    int lowtp, fim;
    string cor;
} vertice;

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


void questao1(digraph& G, digraph& Gt);
void questao2(digraph& G, digraph& G2);
void questao3(digraph& G1, digraph& G2, digraph& Gp);
void questao4(digraph& G);
void questao5_6(digraph& G);




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


// -----------------------------------------------------------------
// ------ MAIN -----------------------------------------------------
// -----------------------------------------------------------------
int main() {
	// Para executar a questao, coloque 1 no vetor abaixo
	// QUESTAO -------- 1 2 3 4 5 6 7 8
	int questao[9] = {0,0,0,0,0,1,1,0,0};
	//int questao[9] = {1,1,1,1,1,1,1,1,1};


    int i,j,k;

    digraph G;
    digraph_create(G);

    if (questao[1])
    {
        cout<<"---------------------------------------------"<<endl;
        cout<<"---------------- QUESTAO 1 ------------------"<<endl;
        cout<<"---------------------------------------------"<<endl;
        digraph Gt;
        questao1(G,Gt);
        //digraph_print(Gt);
        digraph_delete(Gt);
    }

    if (questao[2])
    {
        cout<<"---------------------------------------------"<<endl;
        cout<<"---------------- QUESTAO 2 ------------------"<<endl;
        cout<<"---------------------------------------------"<<endl;
        digraph G2;
        questao2(G,G2);
        //digraph_print(G2);
        digraph_delete(G2);
    }

    if (questao[3])
    {
        cout<<"---------------------------------------------"<<endl;
        cout<<"---------------- QUESTAO 3 ------------------"<<endl;
        cout<<"---------------------------------------------"<<endl;
        digraph Gp;
        questao3(G,G,Gp);
        //digraph_print(Gp);
        digraph_delete(Gp);
    }

    if (questao[4])
    {
        cout<<"---------------------------------------------"<<endl;
        cout<<"---------------- QUESTAO 4 ------------------"<<endl;
        cout<<"---------------------------------------------"<<endl;
        questao4(G);
    }

    if (questao[5] || questao[6])
    {
        cout<<"---------------------------------------------"<<endl;
        cout<<"---------------- QUESTAO 5/6 ----------------"<<endl;
        cout<<"---------------------------------------------"<<endl;
        questao5_6(G);
    }

    if (questao[7])
    {
        cout<<"---------------------------------------------"<<endl;
        cout<<"---------------- QUESTAO 7 ------------------"<<endl;
        cout<<"---------------------------------------------"<<endl;

        cout<<endl;
    }
    if (questao[8])
    {
        cout<<"---------------------------------------------"<<endl;
        cout<<"---------------- QUESTAO 8 ------------------"<<endl;
        cout<<"---------------------------------------------"<<endl;

        cout<<endl;
    }

    digraph_delete(G);
    return 0;
}


// -----------------------------------------------------------------
// ---- QUESTOES DA LISTA 2 DE EXERCICIOS --------------------------
// -----------------------------------------------------------------
void questao1(digraph& G, digraph& Gt) {
    int k,x,y;
    int N = G.N;
    Gt.N = N;
    Gt.V = new vertice[N];

    for (y=0; y<N; y++) {
        Gt.V[y].grau = 0;
    }
    for (x=0; x<N; x++) {
        for (k=0; k<G.V[x].grau; k++) {
            y = G.V[x].adjL[k];
            Gt.V[y].grau++;
        }
    }
    for (y=0; y<N; y++) {
        Gt.V[y].adjL = new int[Gt.V[y].grau];
    }

    int* cont = new int[N]();
    for (x=0; x<N; x++) {
        for (k=0; k<G.V[x].grau; k++) {
            y = G.V[x].adjL[k];
            Gt.V[y].adjL[cont[y]++] = x;
        }
    }
    delete[] cont;
}

void questao2(digraph& G, digraph& G2) {
    int x,z,k,l, N = G.N;
    G2.N = N;
    G2.V = new vertice[N];
    for (x=0; x<N; x++) {
        G2.V[x].grau = 0;
    }

    int* visit = new int[N]();
    for (x=0; x<N; x++) {
        for (k=0; k<G.V[x].grau; k++) {
            int y = G.V[x].adjL[k];
            for (l=0; l<G.V[y].grau; l++) {
                z = G.V[y].adjL[l];
                visit[z] = 1;
            }
        }
        for (z=0; z<N; z++) {
            if (visit[z]==1) G2.V[x].grau++;
        }
        G2.V[x].adjL = new int[G2.V[x].grau];
        k=0;
        for (z=0; z<N; z++) {
            if (visit[z]==1) {
                G2.V[x].adjL[k++] = z;
                visit[z] = 0;
            }
        }
    }
    delete[] visit;
}

void questao3(digraph& G1, digraph& G2, digraph& Gp) {
    int v,x1,x2,k;
    int N1 = G1.N;
    int N2 = G2.N;
    Gp.N = N1 * N2;
    Gp.V = new vertice[Gp.N];

    for (x1=0; x1<N1; x1++) {
        for (x2=0; x2<N2; x2++) {
            v = x1*N2 + x2;
            Gp.V[v].grau = G1.V[x1].grau + G2.V[x2].grau;
            Gp.V[v].adjL = new int[Gp.V[v].grau];
            int loop=0; int h=0;
            for (k=0; k<G2.V[x2].grau; k++) {
                int y2 = G2.V[x2].adjL[k];
                if (x2==y2) loop=1;
                int w = x1*N2 + y2;
                Gp.V[v].adjL[h++] = w;
            }
            for (k=0; k<G1.V[x1].grau; k++) {
                int y1 = G1.V[x1].adjL[k];
                if ((x1==y1)&&(loop)) Gp.V[v].grau--;
                else {
                    int w = y1*N2 + x2;
                    Gp.V[v].adjL[h++] = w;
                }
            }
        }
    }
}

// --------------------------------------------
// Busca em profundidade (original, recursiva)
// --------------------------------------------
void busca_prof_rec(digraph& G, int u, int& tempo) {
    if (G.V[u].cor=="branco") {
        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];
            G.V[v].pai = u;
            busca_prof_rec(G,v,tempo);
        }
        G.V[u].cor = "preto";
        G.V[u].fim = tempo++;
    }
}

int busca_prof(digraph& G) {
    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;
    for (int s=0; s<G.N; s++) {
        busca_prof_rec(G,s,tempo);
    }
    return tempo;
}
void questao4(digraph& G) {
    cout<<"Ordenacao topologica:"<<endl<<endl;
    int tempo_total = busca_prof(G);
    for (int s=0; s<G.N; s++) {
        cout<<"Vertice "<<s<<", Ordem "<<tempo_total-G.V[s].fim<<endl;
    }
}



// --------------------------------------------
// ARTICULACOES E PONTES DE UM GRAFO
// --------------------------------------------
void questao5_6_rec(digraph& G, int x, int& tempo) {
    G.V[x].tempo = ++tempo;
    G.V[x].lowtp = tempo;
    int root; if (G.V[x].pai==x) root=1; else root=0;
    for (int k=0; k<G.V[x].grau; k++) {
        int y = G.V[x].adjL[k];
        if (G.V[y].tempo<=0) {
            G.V[y].pai = x;
            questao5_6_rec(G,y,tempo);
            if (G.V[x].lowtp>G.V[y].lowtp) G.V[x].lowtp = G.V[y].lowtp;
            if (G.V[x].tempo<G.V[y].lowtp) printf("ponte %d-%d\n",x,y);
            if (G.V[x].tempo<=G.V[y].lowtp) {
                if (root==0) {cout<<"articulacao "<<x<<endl;}
                if (root==2) {cout<<"articulacao "<<x<<endl; root=3;}
                if (root==1) root=2;
            }
        } else if (y!=G.V[x].pai) {
            if (G.V[x].lowtp>G.V[y].tempo) G.V[x].lowtp = G.V[y].tempo;
        }
    }
}
void questao5_6(digraph& G) {
    for (int x=0; x<G.N; x++) {
        G.V[x].tempo=0;
    }

    int tempo = 0;
    for (int x=0; x<G.N; x++) {
        if (G.V[x].tempo==0) {
            G.V[x].pai = x;
            questao5_6_rec(G,x,tempo);
        }
    }
}


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


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

    ifstream arq;
    arq.open("entrada_lista2_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;
}