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


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

    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 Tarjan(digraph& G);


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


// ------------------------------------------------------
// ------ MAIN ------------------------------------------
// ------------------------------------------------------
int main() {
    digraph G;
    if (!digraph_create(G)) {cout<<"Arquivo inexistente"; return -1;}
    cout<<"------------------------------------\n";
    cout<<"--- Algoritmo de TARJAN ------------\n";
    cout<<"------------------------------------\n\n";
    cout<<"As componentes fortes do grafo:\n";


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

    digraph_delete(G);
    cout<<"\n\n\n";
    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 Tarjan_rec(digraph& G, int v) {
    list<int>::iterator it;
    Pilha.push(v);
    G.V[v].tempo = tempo;
    G.V[v].lowtp = tempo;
    G.V[v].na_pilha = true;
    tempo++;
    for (it=G.V[v].AdjL.begin(); it!=G.V[v].AdjL.end(); ++it) {
        int w = (*it);
        if (G.V[w].tempo<=0) {
            Tarjan_rec(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<<"\n";
        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 Tarjan(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) Tarjan_rec(G,x);
    }
}

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


// ------------------------------------------------------
// ------------------------------------------------------
int digraph_create(digraph& G) {
    ifstream arq;
    arq.open("entrada_tarjan_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 i=1; i<=grau; i++) {
            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;
}