// ------------------------------------------------------------------------------------------------
// ---- COMPONENTES FORTES DE UM GRAFO DIRECIONADO ------------------------------------------------
// ---- ALGORITMO DE TARJAN -----------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
#include <iostream>
#include <fstream>
#include <cmath>
#include <ctime>
#include <climits>
#include <windows.h>
#include <stack>
using namespace std;


typedef struct vertice {
    int grau;
    int* adj;

    int tempo;
    int lowtp;
    bool na_pilha;
} vertice;

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


// ----------------------------------------
// Componentes fortes (algoritmo de TARJAN)
// ----------------------------------------
void strong_components(digraph& G);


// ---------------------------------------
// Manutenção de grafos
// ---------------------------------------
bool 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"; return -1;}


    // Componentes fortes de um Grafo Direcionado
    // ALGORITMO DE TARJAN
    strong_components(G);

    digraph_delete(G);
    return 0;
}

// ------------------------------------------------------------------------------------------------
// ---- COMPONENTES FORTES DE UM GRAFO ------------------------------------------------------------
// ------------------------------------------------------------------------------------------------

stack<int> Pilha;
int tempo;

// algoritmo auxiliar
// Busca em profundidade marcando tambem o menor tempo encontrado por cada vertice
// Mantem uma pilha com os vertices ainda sem componente
void strong_buscaprof(digraph& G, int v) {
    Pilha.push(v);
    G.V[v].tempo = tempo;
    G.V[v].lowtp = tempo;
    G.V[v].na_pilha = true;
    tempo++;
    for (int k=0; k < G.V[v].grau; k++) {
        int w = G.V[v].adj[k];
        if (G.V[w].tempo<=0) {
            strong_buscaprof(G,w);
            if (G.V[v].lowtp>G.V[w].lowtp) G.V[v].lowtp = G.V[w].lowtp;
        } else if (G.V[w].na_pilha) {
            if (G.V[v].lowtp>G.V[w].tempo) G.V[v].lowtp = G.V[w].tempo;
        }
    }
    if (G.V[v].lowtp==G.V[v].tempo) {
        cout<<endl;
        while (true) {
            int w = Pilha.top(); Pilha.pop();
            G.V[w].na_pilha = false;
            cout << w <<" ";
            if (w==v) break;
        }
    }
}


// Algoritmo principal: Componentes fortes de um grafo direcionado
// Algoritmo de TARJAN
void strong_components(digraph& G) {
    tempo = 0;
    for (int x=0; x<G.N; x++) {
        G.V[x].tempo = 0;
        G.V[x].lowtp = 0;
        G.V[x].na_pilha = false;
    }

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

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


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

    ifstream arq;
    arq.open("entrada_tarjan_adjL.txt");
    if (arq.fail()) return false;
    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].adj = new int[grau];
        for (int k=0; k<grau; k++) {
            arq >> G.V[i].adj[k];
        }
    }
    arq.close();
    return true;
}

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