/*
 *  cfc.c
 *
 *  Componenti Fortemente Connesse di un grafo orientato.
 *
 *  #(@) 20081020 (liverani@mat.uniroma3.it)
 */
 
#include <stdlib.h>
#include <stdio.h>
#include "grafi.h"

void visita(grafo G, elementoLista **f, int i, int c[]) {
  elementoLista *p;
  c[i] = 1;
  p = G.V[i];
  while (p != NULL) {
    if (c[p->info] == 0) {
      visita(G, f, p->info, c);
    }
    p = p->next;
  }
  *f = impila(*f, i);
  return;
}

void dfs(grafo G, elementoLista **f) {
  int *c, i;
  c = malloc(sizeof(int)*(G.n+1));
  for (i=1; i<=G.n; i++) {
    c[i] = 0;
  }
  for (i=1; i<=G.n; i++) {
    if (c[i] == 0) {
      visita(G, f, i, c);
    }
  }
  return;
}

void visitaBis(grafo G, int i, int c[]) {
  elementoLista *p;
  c[i] = 1;
  p = G.V[i];
  printf("%d ", i);
  while (p != NULL) {
    if (c[p->info] == 0) {
      visitaBis(G, p->info, c);
    }
    p = p->next;
  }
  return;
}

/*
 *  funzione principale
 *
 *  Calcola le componenti fortemente connesse del grafo orientato G
 *  utilizzando il seguente algoritmo:
 *  1. Esegue una visita in profondita' (DFS) di G e calcola i tempi
 *     di fine visita (in realta' inserisce i vertici di G in una pila
 *     in base all'ordine di fine della visita)
 *  2. Calcola le liste di adiacenza del grafo trasposto GT, ottenuto 
 *     invertendo il verso degli spigoli di G
 *  3. Esegue una visita in profondita' del grafo trasposto, considerando
 *     i vertici nell'ordine decrescente di tempo di completamento della
 *     visita calcolato al passo 1. Gli alberi di visita individuati in GT
 *     sono le componenti fortemente connesse di G.
 */
 
int main(void) {
  grafo G, GT;
  elementoLista *f;
  int i, *c, cont = 1;
  leggiGrafo(&G);
  printf("\nListe di adiacenza del grafo G:\n");
  stampaGrafo(G);
  
/*  PASSO 1 */
  dfs(G, &f);
  printf("\nOrdine dei vertici di G in base al tempo di fine visita:\n");
  stampaLista(f);
  
/*  PASSO 2 */
  grafoTrasposto(G, &GT);
  printf("\nListe di adiacenza del grafo trasposto GT:\n");
  stampaGrafo(GT);
  
/*  PASSO 3 */
  printf("\nComponenti fortemente connesse del grafo G:\n");
  c = malloc(sizeof(int)*(G.n+1));
  for (i=1; i<=GT.n; i++)
    c[i] = 0;
  while (f != NULL) {
    if (c[f->info] == 0) {
      printf("  Componente n.%d = { ", cont++);
      visitaBis(GT, f->info, c);
      printf("}\n");
    }
    f = f->next;
  }
  return(0);
}