// ------------------------------------------------------------------------------------------------
// ---- BUSCA EM PROFUNDIDADE E EM LARGURA --------------------------------------------------------
// ------------------------------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>



typedef struct digraph {
	int N;// numero de vertices
	int M;// numero de arestas
	int* grau;// vetor de graus
	int** adjL;// Lista de adjacencias
	int* adjM;// Matriz de adjacencias
} digraph;


void questao1(digraph* G, digraph* Gt);
void questao2a(digraph* G, digraph* G2);
void questao2b(digraph* G, digraph* G2);
void questao3(digraph* G1, digraph* G2, digraph* Gq);
void questao4(digraph* G);
void questao5_6(digraph* G);




void digraph_create(digraph* G, int tipo);
void digraph_delete(digraph* G, int tipo);
void digraph_print(digraph* G, int tipo);
int get(digraph* G, int x, int y);
void set(digraph* G, int x, int y, int novo);


typedef struct pilha {
    int* vet;//pilha de inteiros
    int topo;// pilha topo
    int tam;// pilha tamanho
} pilha;

bool Push(pilha* P, int x);
int Pop(pilha* P);
bool pilha_vazia(pilha* P);
bool pilha_cheia(pilha* P);
void pilha_create(pilha* P, int N);
void pilha_delete(pilha* P);

// ------------------------------------------------------------------------------------------------
// ------ MAIN ------------------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
int main() {
    int i,j,k;

    digraph G,Gt,G2,Gq;
    digraph_create(&G,2);// lista de adj por arquivo


    //questao1(&G,&Gt); //digraph_print(&Gt,1);
    //questao2a(&G,&G2); //digraph_print(&G2,1);
    //questao3(&G,&G,&Gq); digraph_print(&Gq,1);
    //questao4(&G);
    questao5_6(&G);


    digraph_delete(&G,1);
    //digraph_delete(&Gt,1);
    //digraph_delete(&G2,1);
    //digraph_delete(&Gq,1);
    return 1;
}


// ------------------------------------------------------------------------------------------------
// ---- QUESTOES DA LISTA 2 DE EXERCICIOS ---------------------------------------------------------
// ------------------------------------------------------------------------------------------------
void questao1(digraph* G, digraph* Gt) {
    int x,k, N = G->N;
    Gt->N = N;
    Gt->grau = (int*) calloc(N,sizeof(int));
    Gt->adjL = (int**) malloc(N * sizeof(int*));

    for (x=0; x<N; x++) {
        for (k=0; k<G->grau[x]; k++) {
            int y = G->adjL[x][k];
            Gt->grau[y]++;
        }
    }
    for (x=0; x<N; x++) {
        Gt->adjL[x] = (int*) malloc(Gt->grau[x] * sizeof(int));
    }

    int* cont = (int*) calloc(N,sizeof(int));
    for (x=0; x<N; x++) {
        for (k=0; k<G->grau[x]; k++) {
            int y = G->adjL[x][k];
            Gt->adjL[y][cont[y]++] = x;
        }
    }
    free(cont);
}

void questao2a(digraph* G, digraph* G2) {
    int x,z,k,l, N = G->N;
    G2->N = N;
    G2->grau = (int*) calloc(N,sizeof(int));
    G2->adjL = (int**) malloc(N * sizeof(int*));

    int* visit = (int*) calloc(N,sizeof(int));
    for (x=0; x<N; x++) {
        for (k=0; k<G->grau[x]; k++) {
            int y = G->adjL[x][k];
            for (l=0; l<G->grau[y]; l++) {
                z = G->adjL[y][l];
                visit[z] = 1;
            }
        }
        for (z=0; z<N; z++) {
            if (visit[z]==1) G2->grau[x]++;
        }
        G2->adjL[x] = (int*) malloc(G2->grau[x] * sizeof(int));
        k=0;
        for (z=0; z<N; z++) {
            if (visit[z]==1) {
                G2->adjL[x][k++] = z;
                visit[z] = 0;
            }
        }
    }
    free(visit);
}

void questao2b(digraph* G, digraph* G2) {
    int x,y,z, N = G->N;
    G2->N = N;
    G2->adjM = (int*) calloc(ceil(N*N/32.0), sizeof(int));

    for (x=0; x<N; x++) {
        for (y=0; y<N; y++) {
            if (get(G,x,y)==1) {
                for (z=0; z<N; z++) {
                    if (get(G,y,z)==1) {
                        set(G2,x,z,1);
                    }
                }
            }
        }
    }
}

void questao3(digraph* G1, digraph* G2, digraph* Gq) {
    int v,x1,x2,k;
    int N1 = G1->N;
    int N2 = G2->N;
    Gq->N = N1 * N2;
    Gq->grau = (int*) calloc(Gq->N,sizeof(int));
    Gq->adjL = (int**) malloc(Gq->N * sizeof(int*));

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

// busca_prof
bool questao4_rec(digraph* G, int x, int* tempo, int* na_pilha, int* tempo_total, pilha* P) {
    tempo[x] = ++(*tempo_total);
    int k;
    for (k=0; k<G->grau[x]; k++) {
        int y = G->adjL[x][k];
        if (tempo[y]<=0) {
            if (! questao4_rec(G,y,tempo,na_pilha,tempo_total,P)) return false;
        } else if (na_pilha[y]==0) {
            printf("\nCiclo direcionado encontrado: %d <-> %d \n",y,x);
            return false;
        }
    }
    na_pilha[x] = 1;
    Push(P,x);
    return true;
}
void questao4(digraph* G) {
    int x, N = G->N;
    int tempo_total = 0;
    int* tempo = (int*) calloc(N,sizeof(int));
    int* na_pilha = (int*) calloc(N,sizeof(int));
    pilha P; pilha_create(&P,N);
    for (x=0; x<N; x++) {
        if (tempo[x]==0) {
            if (!questao4_rec(G,x,tempo,na_pilha,&tempo_total,&P)) {
                free(tempo); free(na_pilha);
                pilha_delete(&P);
                return;
            }
        }
    }
    printf("\n");
    while (!pilha_vazia(&P)) {
        printf("%d,",Pop(&P));
    }
    free(tempo); free(na_pilha);
    pilha_delete(&P);
}

// busca_prof
void questao5_6_rec(digraph* G, int x, int* tempo, int* lowtp, int* pai, int* tempo_total) {
    tempo[x] = ++(*tempo_total);
    lowtp[x] = tempo[x];
    int k,root; if (pai[x]==x) root=1; else root=0;
    for (k=0; k<G->grau[x]; k++) {
        int y = G->adjL[x][k];
        if (tempo[y]<=0) {
            pai[y] = x;
            questao5_6_rec(G,y,tempo,lowtp,pai,tempo_total);
            if (lowtp[x]>lowtp[y]) lowtp[x] = lowtp[y];
            if (tempo[x]<lowtp[y]) printf("ponte %d-%d\n",x,y);
            if (tempo[x]<=lowtp[y]) {
                if (root==0) {printf("articulacao %d\n",x);}
                if (root==2) {printf("articulacao %d\n",x); root=3;}
                if (root==1) root=2;
            }
        } else if (y!=pai[x]) {
            if (lowtp[x]>tempo[y]) lowtp[x] = tempo[y];
        }
    }
}
void questao5_6(digraph* G) {
    int x, N = G->N;
    int tempo_total = 0;
    int* tempo = (int*) calloc(N,sizeof(int));
    int* lowtp = (int*) calloc(N,sizeof(int));
    int* pai = (int*) calloc(N,sizeof(int));
    for (x=0; x<N; x++) {
        if (tempo[x]==0) {
            pai[x] = x;
            questao5_6_rec(G,x,tempo,lowtp,pai,&tempo_total);
        }
    }
    free(tempo); free(lowtp); free(pai);
}


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


// ------------------------------------
// tipo: 2 (arquivo adjL)
// ------------------------------------
void digraph_create(digraph* G, int tipo) {
    G->N=0; G->M=0;
    G->adjM=NULL; G->adjL=NULL; G->grau=NULL;

    int i,j,k,N;
    tipo = 2;
    if (tipo==2) {
        FILE* arq = fopen("entrada_digraph_adjL.txt", "r");
        fscanf(arq,"%d",&N);
        G->N=N;

        // Graus dos vertices
        G->grau = (int*) calloc(N, sizeof(int));
        for (i=0;i<N;i++) {
            int aux;
            fscanf(arq,"%d",&aux);
            G->grau[i] = aux;
            G->M += aux;
        }
        // Listas de adjacencias
        G->adjL = (int**) malloc(N * sizeof(int*));
        for (i=0;i<N;i++) {
            G->adjL[i] = (int*) malloc(G->grau[i] * sizeof(int));
            for (k=0; k<G->grau[i]; k++) {
                int aux;
                fscanf(arq,"%d",&aux);
                G->adjL[i][k] = aux;
            }
        }
    }
}

// ------------------------------------
// tipo: 0 (adjM), 1 (adjL)
// ------------------------------------
void digraph_delete(digraph* G, int tipo) {
    int i;
    int N = G->N;
    if (tipo==0) {
        if (G->adjM != NULL) free(G->adjM);
        G->adjM = NULL;
    }
    if (tipo==1) {
        if (G->grau != NULL) {
            free(G->grau);
            G->grau = NULL;
        }

        if (G->adjL != NULL) {
            for (i=0;i<N;i++) {
                if (G->adjL[i] != NULL) {
                    free(G->adjL[i]);
                    G->adjL[i] = NULL;
                }
            }
            free(G->adjL);
            G->adjL = NULL;
        }
    }
}
void digraph_print(digraph* G, int tipo) {
    bool tela = true;
    int i,j,k, N=G->N;
    if (tipo==0) {
        if (tela) {
            for (i=0;i<N;i++) {
                for (j=0;j<N;j++) {
                    int aux = get(G,i,j);
                    printf("%d ",aux);
                }
                int aux = get(G,i,N-1);
                printf("%d",aux);
            }
        }
    }
    if (tipo==1) {
        if (tela) {
            printf("%d\n",N);
            for (i=0;i<N;i++) printf("%d ",G->grau[i]);
            printf("\n");
            for (i=0;i<N;i++) {
                printf("\n");
                for (k=0;k<G->grau[i]-1;k++) {
                    printf("%d ",G->adjL[i][k]);
                }
                if (G->grau[i]>0) printf("%d",G->adjL[i][G->grau[i]-1]);
            }
            printf("\n");
        }
    }
}

int get(digraph* G, int x, int y) {
	int pos  = x*G->N+y;
	int k  = (int) (pos/32.0);
	int rk = pos%32;

	// A informacao estah no bit rk de A[k] (os bits vao de 0 a 31)
	int bit = (G->adjM[k]&(1<<rk))!=0;
	return bit;
}

void set(digraph* G, int x, int y, int novo) {
	if ((novo!=0)&&(novo!=1)) return;
	int pos  = x*G->N+y;
	int k  = (int) (pos/32.0);
	int rk = pos%32;

	// A informacao estah no bit rk de A[k] (os bits vao de 0 a 31)
	int bit = (G->adjM[k]&(1<<rk))!=0;
	if (novo==bit) return;
	if (novo==0) G->adjM[k] -= (1<<rk);
	else G->adjM[k] |= (1<<rk);
}





// ------------------------------------------------------------------------------------------------
// ---- MANUTENÇÃO DE PILHAS ----------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
bool Push(pilha* P, int x) {
    if (pilha_cheia(P)) return false;
    P->vet[++P->topo] = x;
    return true;
}

int Pop(pilha* P) {
    if (pilha_vazia(P)) {
            printf("Pilha Vazia (estouro negativo)\n");
            return -1;
    }
    return P->vet[P->topo--];
}

void pilha_create(pilha* P, int N) {
    P->vet = NULL;
    P->tam = 0;
    P->topo = -1;
    if (N<=0) return;
    P->tam = N;
    P->vet = (int*) calloc(N,sizeof(int));
}

void pilha_delete(pilha* P) {
    if (P->vet==NULL) return;
    free(P->vet);
    P->vet = NULL;
    P->tam = 0;
    P->topo = -1;
}

bool pilha_vazia(pilha* P) {
    if (P->topo<0) return true;
    return false;
}

bool pilha_cheia(pilha* P) {
    if (P->topo>=P->tam-1) return true;
    return false;
}