// ------------------------------------------------------------------
// --- TODAS AS ARTICULACOES E PONTES DE UM GRAFO NAO-DIRECIONADO ---
// ------------------------------------------------------------------
#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;
    int pai;
} vertice;

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


// ----------------------------------------
// Articulacoes e pontes de um grafo
// ----------------------------------------
int Grafo_NaoDir(digraph& G);
void Artic_Pontes(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\n\n"; return -1;}
    cout<<"--------------------------------------------------------------------\n";
    cout<<"--- Todas as Articulacoes e Pontes de um grafo Nao-Direcionado -----\n";
    cout<<"--------------------------------------------------------------------\n\n";
    cout<<"\n";

    if (!Grafo_NaoDir(G)) {cout<<"Grafo Direcionado\n\n"; return -1;}
    Artic_Pontes(G);


    digraph_delete(G);
    cout<<"\n\n\n";
    return 0;
}

// ------------------------------------------------------------
// ---- ARTICULACOES E PONTES DE UM GRAFO NAO-DIRECIONADO -----
// ------------------------------------------------------------

int tempo;

// ------------------------------------------------------
// algoritmo auxiliar
// Busca em profundidade marcando tambem o menor tempo encontrado por cada vertice
// Impede o vertice de voltar pelo vertice pai
// ------------------------------------------------------
void Artic_Pontes_rec(digraph& G, int x) {
    list<int>::iterator it;
    G.V[x].tempo = ++tempo;
    G.V[x].lowtp =   tempo;
    int root; if (G.V[x].pai==x) root=1; else root=0;
    for (it=G.V[x].AdjL.begin(); it!=G.V[x].AdjL.end(); ++it) {
        int y = (*it);
        if (G.V[y].tempo<=0) {
            G.V[y].pai = x;
            Artic_Pontes_rec(G,y);
            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; root=2;}
                if (root==1) root=0;
            }
        } else if (y!=G.V[x].pai) {
            if (G.V[x].lowtp>G.V[y].tempo) G.V[x].lowtp = G.V[y].tempo;
        }
    }
}

// -------------------------------------------------------------------
// Algoritmo principal: Articulacoes e pontes de grafo nao-direcionado
// -------------------------------------------------------------------
void Artic_Pontes(digraph& G) {
    for (int x=0; x<G.N; x++) {
        G.V[x].tempo=0;
    }
    tempo = 0;
    for (int x=0; x<G.N; x++) {
        if (G.V[x].tempo==0) {
            G.V[x].pai = x;
            Artic_Pontes_rec(G,x);
        }
    }
}

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


int Grafo_NaoDir(digraph& G) {
    list<int>::iterator it;
    int x,y,N = G.N;
    int** A = new int*[N];

    for (x=0; x<N; x++) {
        A[x] = new int[N]();// inicializa com 0s
        for (it=G.V[x].AdjL.begin(); it!=G.V[x].AdjL.end(); ++it) {
            y = (*it);
            A[x][y] = 1;
        }
    }
    int naodir = 1;
    for (x=0; x<N; x++) {
        for (it=G.V[x].AdjL.begin(); it!=G.V[x].AdjL.end(); ++it) {
            y = (*it);
            if (A[y][x]==0) {naodir = 0; break;}
        }
        if (!naodir) break;
    }
    for (x=0; x<N; x++) delete A[x];
    delete A;
    return naodir;
}

// ------------------------------------------------------
// ------------------------------------------------------
int digraph_create(digraph& G) {
    ifstream arq;
    //arq.open("entrada_tarjan_adjL.txt");
    arq.open("entrada_articpont_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;
}