// -----------------------------------------------------------------
// ---- CODIGOS DOS EXERCICIOS DA LISTA 3 --------------------------
// -----------------------------------------------------------------
#include <iostream>
#include <fstream>
#include <ctime>
#include <stack>
#include <vector>
using namespace std;


class grafo {

public:
    int N;// numero de vertices
    int M;// numero de arestas
    vector<vector < int >> adjL;

    grafo();     //construtor1 (ler grafo do arquivo "grafo.txt")
    grafo(int n);//construtor2 (cria grafo com n vertices e nenhuma aresta)

    void imprime();

    void lista_para_matriz();
    void matriz_para_lista();
    bool direcionado();
    void transposto();
    void quadrado();
    void produto_cartesiano(grafo& G1, grafo& G2);
    void ordem_topologica();

private:
    bool visita(int x, vector<int>& status, stack<int>& ordem);
    void inclui_aresta(int x, int y);// Adiciona aresta de x p/ y (se nao existe)
};

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



    if (questao[3])
    {
        cout<<"---------------------------------------------------------\n";
        cout<<"---- QUESTAO 3 (lista ADJ -> matriz ADJ) ----------------\n";
        cout<<"---------------------------------------------------------\n";
        grafo G;
        G.imprime();

        G.lista_para_matriz();
        cout<<"\n\n\n";
    }
    if (questao[4])
    {
        cout<<"---------------------------------------------------------\n";
        cout<<"---- QUESTAO 4 (matriz ADJ -> lista ADJ) ----------------\n";
        cout<<"---------------------------------------------------------\n";
        grafo G(15);

        G.matriz_para_lista();
        cout<<"\n\n\n";
    }
    if (questao[5])
    {
        cout<<"---------------------------------------------------------\n";
        cout<<"---- QUESTAO 5 (direcionado ou nao) ---------------------\n";
        cout<<"---------------------------------------------------------\n";
        grafo G;
        G.imprime();

        if (G.direcionado())
            cout<<"Esse grafo NAO representa um grafo nao-direcionado";
        else
            cout<<"Esse grafo representa SIM um grafo nao-direcionado";

        cout<<"\n\n\n";
    }
    if (questao[6])
    {
        cout<<"---------------------------------------------------------\n";
        cout<<"---- QUESTAO 6 (transposto de um grafo) -----------------\n";
        cout<<"---------------------------------------------------------\n";
        grafo G;
        G.imprime();

        G.transposto();
        cout<<"\n\n\n";
    }
    if (questao[7])
    {
        cout<<"---------------------------------------------------------\n";
        cout<<"---- QUESTAO 7 (quadrado de um grafo) -------------------\n";
        cout<<"---------------------------------------------------------\n";
        grafo G;
        G.imprime();

        G.quadrado();
        cout<<"\n\n\n";
    }
    if (questao[8])
    {
        cout<<"---------------------------------------------------------\n";
        cout<<"---- QUESTAO 8 (produto cartesiano de 2 grafos) ---------\n";
        cout<<"---------------------------------------------------------\n";
        grafo G;
        G.imprime();

        grafo Gp(0);
        Gp.produto_cartesiano(G,G);
        Gp.imprime();
        cout<<"\n\n\n";
    }
    if (questao[9])
    {
        cout<<"---------------------------------------------------------\n";
        cout<<"---- QUESTAO 9 (ordenacao topologica) -------------------\n";
        cout<<"---------------------------------------------------------\n";
        grafo G;
        G.imprime();

        G.ordem_topologica();
        cout<<"\n\n\n";
    }
    if (questao[10])
    {
        cout<<"---------------------------------------------------------\n";
        cout<<"---- QUESTAO 10 (Dijkstra com matriz de adjacencias) ----\n";
        cout<<"---------------------------------------------------------\n";
        //grafo2 G;
        //G.imprime();
        //G.dijkstra2();
        cout<<"\n\n\n";
    }
    return 0;
}


// -----------------------------------------------------------------
// ---- ALGORITMOS DA CLASSE GRAFO ---------------------------------
// -----------------------------------------------------------------
void grafo::lista_para_matriz() {
    vector<vector<int>> matriz;
    matriz.resize(N);

    for (int x=0; x<N; x++) {
        matriz[x].resize(N);
        int grau_x = adjL[x].size();
        for (int i=0; i<grau_x; i++) {
            int y = adjL[x][i];
            matriz[x][y] = 1;
        }
    }
    for (int x=0; x<N; x++) {
        for (int y=0; y<N; y++)
            cout << matriz[x][y] << " ";

        cout << "\n";
    }
}


void grafo::matriz_para_lista() {
    srand (time(NULL));
    vector<vector<int>> matriz;
    matriz.resize(N);

    for (int x=0; x<N; x++) {
        matriz[x].resize(N);
        for (int y=0; y<N; y++) {
            matriz[x][y] = rand()%2 * (x!=y);
        }
    }

    adjL.clear();
    adjL.resize(N);
    for (int x=0; x<N; x++) {
        for (int y=0; y<N; y++) {
            if (matriz[x][y]==1) {
                adjL[x].push_back(y);
            }
        }
    }
    imprime();
}


bool grafo::direcionado() {
    int x,y = N;
    vector<vector<int>> A;
    A.resize(N);

    for (x=0; x<N; x++) {
        A[x].resize(N);// inicializa com 0s
        for (int i=0; i<adjL[x].size(); i++) {
            y = adjL[x][i];
            A[x][y] = 1;
        }
    }
    bool dir = false;
    for (x=0; x<N; x++) {
        for (int i=0; i<adjL[x].size(); i++) {
            y = adjL[x][i];
            if (A[y][x]==0) {dir = true; break;}
        }
        if (dir) break;
    }
    return dir;
}




void grafo::transposto() {
    grafo T(N);

    for (int x=0; x<N; x++) {
        int grau_x = adjL[x].size();
        for (int i=0; i<grau_x; i++) {
            int y = adjL[x][i];
            T.inclui_aresta(y,x);
        }
    }
    T.imprime();
}




void grafo::quadrado() {
    grafo Q(N);

    for (int x=0; x<N; x++) {
        int grau_x = adjL[x].size();
        for (int i=0; i<grau_x; i++) {
            int y = adjL[x][i];
            int grau_y = adjL[y].size();
            for (int j=0; j<grau_y; j++) {
                int z = adjL[y][j];
                Q.inclui_aresta(x,z);
            }
        }
    }
    Q.imprime();
}



void grafo::produto_cartesiano(grafo& G1, grafo& G2) {
    int N1 = G1.N;
    int N2 = G2.N;

    N = N1*N2;
    adjL.clear();
    adjL.resize(N);

    for (int x1=0; x1<N1; x1++) {//para cada vertice x1 de G1
        for (int x2=0; x2<N2; x2++) {//para cada vertice x2 de G2
            int x = x1*N2 + x2;//seja x=(x1,x2) o vertice de G (produto cartesiano)

            int grau_x1 = G1.adjL[x1].size();
            for (int i=0; i<grau_x1; i++) {
                int y1 = G1.adjL[x1][i];// para cada vizinho y1 de x1 em G1
                int y = y1*N2 + x2;// inclua a aresta (x1,x2)-(y1,x2)
                inclui_aresta(x,y);
            }

            int grau_x2 = G2.adjL[x2].size();
            for (int j=0; j<grau_x2; j++) {
                int y2 = G2.adjL[x2][j];// para cada vizinho y2 de x2 em G2
                int y = x1*N2 + y2;// inclua a aresta (x1,x2)-(x1,y2)
                inclui_aresta(x,y);
            }
        }
    }
}




// Busca em profundidade
void grafo::ordem_topologica() {
    vector<int> status(N,0);
    stack <int> ordem;

    for (int i=0; i<N; i++) {
        if (status[i]==0) {
            if (! visita(i, status, ordem)) {
                cout << "Tem ciclo direcionado (ou seja, nao tem ordenacao topologica)\n\n\n";
                return;
            }
        }
    }
    while (!ordem.empty()) {
        cout << ordem.top() << " ";
        ordem.pop();
    }
    cout << "\n\n\n";
}

// Busca em profundidade (original, recursiva)
bool grafo::visita(int x, vector<int>& status, stack<int>& ordem) {

    if (status[x]==1) return false;// encontrou um vertice ainda ativo (ciclo direcionado)
    if (status[x]==2) return true;// encontrou um vertice finalizado (nao precisa visitar de novo)
    status[x] = 1;

    int grau_x = adjL[x].size();
    for (int i=0; i<grau_x; ++i) {
        int y = adjL[x][i];
        if (! visita(y, status, ordem))
            return false;
    }
    status[x] = 2;
    ordem.push(x);
    return true;
}





// Construtor da classe
// Faz a leitura do arquivo "grafo.txt"
// Ver o arquivo para entender o formato de entrada, similar a lista de adjacencias
grafo::grafo() {
    N = M = 0;
    ifstream arq;
    int x, y, grau;
    arq.open("grafo.txt");
    if (arq.fail()) return;
    arq >> N;
    adjL.resize(N);

    for (x=0; x<N; x++) {
        arq >> grau;
        M += grau;
        for (int k=0; k<grau; k++) {
            arq >> y;
            adjL[x].push_back(y);
        }
    }
    arq.close();
}

grafo::grafo(int n) {
    N = n;
    adjL.resize(N);
}

void grafo::imprime() {
    cout << "N = " << N << "\n";

    for (int x=0; x<N; x++) {
        cout << "Arestas do vertice " << x << ": ";

        int grau_x = adjL[x].size();
        for (int i=0; i<grau_x; i++) {
            int y = adjL[x][i];
            cout << y << " ";
        }
        cout << "\n";
    }
    cout << "\n\n\n";
}


void grafo::inclui_aresta(int x, int y) {
    if (x==y) return;
    if ((x>=N)||(y>=N)) return;

    int grau_x = adjL[x].size();
    for (int i=0; i<grau_x; i++) {
        int z = adjL[x][i];
        if (y==z) return;
    }
    adjL[x].push_back(y);
}