#include<stdlib.h>
#include<stdio.h>

#define MAXNUMVERTICES  100
#define MAXNUMARESTAS   100
#define TRUE            1
#define FALSE           0

typedef int TipoValorVertice;
typedef int TipoPeso;
typedef struct TipoGrafo {
  TipoPeso Mat[MAXNUMVERTICES + 1][MAXNUMVERTICES + 1];
  char NumVertices;
  char NumArestas;
} TipoGrafo;
typedef int TipoApontador;
typedef enum {
  branco, cinza, preto
}TipoCor;
typedef short TipoValorTempo;

TipoApontador Aux;
short i;
int NVertices, NArestas;
TipoValorVertice V1, V2, Adj;
TipoPeso Peso;
TipoGrafo Grafo, Grafot;
short FimListaAdj;

void FGVazio(TipoGrafo *Grafo)
{ short i, j;
  for (i = 0; i <=Grafo->NumVertices; i++) 
    { for (j = 0; j <=Grafo->NumVertices; j++)
        Grafo->Mat[i][j] = 0;
    }
}

void InsereAresta(TipoValorVertice *V1, TipoValorVertice *V2,
             TipoPeso *Peso, TipoGrafo *Grafo)
{ Grafo->Mat[*V1][*V2] = *Peso;
}

char ExisteAresta(TipoValorVertice Vertice1,
                TipoValorVertice Vertice2, TipoGrafo *Grafo)
{ return (Grafo->Mat[Vertice1][Vertice2] > 0);
}  /* ExisteAresta */

/*-- Operadores para obter a lista de adjacentes --*/
char ListaAdjVazia(TipoValorVertice *Vertice, TipoGrafo *Grafo)
{ TipoApontador Aux = 0;
  char ListaVazia = TRUE;
  while (Aux < Grafo->NumVertices && ListaVazia) 
    { if (Grafo->Mat[*Vertice][Aux] > 0) ListaVazia = FALSE;
      else Aux++;
    }
  return (ListaVazia == TRUE);
}  /* ListaAdjVazia */

TipoApontador PrimeiroListaAdj(TipoValorVertice *Vertice, TipoGrafo *Grafo)
{ TipoValorVertice Result;
  TipoApontador Aux = 0;
  char Listavazia = TRUE;
  while (Aux < Grafo->NumVertices && Listavazia) 
    { if (Grafo->Mat[*Vertice][Aux] > 0) 
      { Result = Aux;
        Listavazia = FALSE;
      } 
      else Aux++;
    }
  if (Aux == Grafo->NumVertices)
  printf("Erro: Lista adjacencia vazia (PrimeiroListaAdj)\n");
  return Result;
}  /* PrimeiroListaAdj */

void ProxAdj(TipoValorVertice *Vertice, TipoGrafo *Grafo,
            TipoValorVertice *Adj, TipoPeso *Peso, TipoApontador *Prox,
            short *FimListaAdj)
{ /* --Retorna Adj apontado por Prox--*/
  *Adj = *Prox;
  *Peso = Grafo->Mat[*Vertice][*Prox];
  (*Prox)++;
  while (*Prox < Grafo->NumVertices && Grafo->Mat[*Vertice][*Prox] == 0)
    (*Prox)++;
  if (*Prox == Grafo->NumVertices)
  *FimListaAdj = TRUE;
}  /* ProxAdj- */

void RetiraAresta(TipoValorVertice *V1, TipoValorVertice *V2,
             TipoPeso *Peso, TipoGrafo *Grafo)
{ if (Grafo->Mat[*V1][*V2] == 0)
  printf("Aresta nao existe\n");
  else 
  { *Peso = Grafo->Mat[*V1][*V2];
    Grafo->Mat[*V1][*V2] = 0;
  }
}  /* RetiraAresta */

void LiberaGrafo(TipoGrafo *Grafo)
{  /* Nao faz nada no caso de matrizes de adjacencia */
}  /* LiberaGrafo */


 void ImprimeGrafo(TipoGrafo *Grafo)
{ short i, j;
  printf("   ");
  for (i = 0; i <= Grafo->NumVertices - 1; i++)
    printf("%3d", i);
  putchar('\n');
  for (i = 0; i <= Grafo->NumVertices - 1; i++) 
    { printf("%3d", i);
      for (j = 0; j <= Grafo->NumVertices - 1; j++)
        printf("%3d", Grafo->Mat[i][j]);
      putchar('\n');
    }
}  /* ImprimeGrafo */

/* Local variables for VisitaDfs: */
struct LOC_VisitaDfs {
  struct LOC_BuscaEmProfundidade *LINK;
  TipoValorVertice u;
} ;

void VisitaDfs(TipoValorVertice u, TipoGrafo *Grafo,
           TipoValorTempo* Tempo, 
           TipoValorTempo* d, 
           TipoValorTempo* t,
           TipoCor* Cor, short* Antecessor)
{ short FimListaAdj;
  TipoPeso Peso;
  TipoApontador Aux;
  TipoValorVertice v;
  Cor[u] = cinza;
  (*Tempo)++;
  d[u] = (*Tempo);
  printf("Visita%2d Tempo descoberta:%2d cinza\n", u, d[u]);
  scanf("%*[^\n]");
  getchar();
  if (!ListaAdjVazia(&u, Grafo)) 
  { Aux = PrimeiroListaAdj(&u, Grafo);
    FimListaAdj = FALSE;
    while (!FimListaAdj) 
      { ProxAdj(&u, Grafo, &v, &Peso, &Aux, &FimListaAdj);
        if (Cor[v] == branco) 
        { Antecessor[v] = u;
          VisitaDfs(v, Grafo, Tempo, d, t, Cor, Antecessor);
        }
      }
  }
  Cor[u] = preto;
  (*Tempo)++;
  t[u] = (*Tempo);
  printf("Visita%2d Tempo termino:%2d preto\n", u, t[u]);
  scanf("%*[^\n]");
  getchar();
}  /* VisitaDfs */

void BuscaEmProfundidade(TipoGrafo *Grafo)
{ TipoValorTempo Tempo;
  TipoValorTempo d[MAXNUMVERTICES + 1], t[MAXNUMVERTICES + 1];
  TipoCor Cor[MAXNUMVERTICES + 1];
  short Antecessor[MAXNUMVERTICES + 1];
  TipoValorVertice x; 
  Tempo = 0;
  for (x = 0; x <= (Grafo->NumVertices) - 1; x++) 
    { Cor[x] = branco;
      Antecessor[x] = -1;
    }
  for (x = 0; x <=Grafo->NumVertices - 1; x++) 
    { if (Cor[x] == branco)
      VisitaDfs(x, Grafo, &Tempo, d, t, Cor, Antecessor);
    }
}  /* BuscaEmProfundidade */

void GrafoTransposto(TipoGrafo *Grafo, TipoGrafo *GrafoT)
{ TipoValorVertice v, Adj;
  TipoPeso Peso; TipoApontador Aux;
  FGVazio(GrafoT);
  GrafoT->NumVertices = Grafo->NumVertices;
  GrafoT->NumArestas = Grafo->NumArestas;
  for (v = 0; v <=Grafo->NumVertices - 1; v++) 
    { if (!ListaAdjVazia(&v, Grafo)) 
      { Aux = PrimeiroListaAdj(&v, Grafo);
        FimListaAdj = FALSE;
        while (!FimListaAdj) 
          { ProxAdj(&v, Grafo, &Adj, &Peso, &Aux, &FimListaAdj);
            InsereAresta(&Adj, &v, &Peso, GrafoT);
          }
      }
    }
}  /* GrafoTransposto */

int main()
{  /*-- Programa principal --*/
  int TEMP, TEMP1;
  /* -- NumVertices: definido antes da leitura das arestas --*/
  /* -- NumArestas: inicializado com zero e incrementado a --*/
  /* -- cada chamada de InsereAresta                       --*/
  printf("No. vertices:");
  scanf("%d%*[^\n]", &TEMP);
  getchar();
  NVertices = TEMP;
  printf("No. arestas:");
  scanf("%d%*[^\n]", &TEMP);
  getchar();
  NArestas = TEMP;
  Grafo.NumVertices = NVertices;
  Grafo.NumArestas = 0;
  FGVazio(&Grafo);
  for (i = 0; i <= NArestas - 1; i++) 
    { printf("Insere V1 -- V2 -- Aresta:");
      scanf("%d%d%d%*[^\n]", &TEMP, &TEMP1, &Peso);
      getchar();
      V1 = TEMP;
      V2 = TEMP1;
      Grafo.NumArestas++;
      InsereAresta(&V1, &V2, &Peso, &Grafo);   /*1 chamada : G direcionado*/
      /*InsereAresta(V2, V1, Peso, Grafo);*/
      /*2 chamadas: G nao-direcionado*/
    }
  ImprimeGrafo(&Grafo);
  scanf("%*[^\n]");
  getchar();
  BuscaEmProfundidade(&Grafo);
  scanf("%*[^\n]");
  getchar();
  printf("Grafo transposto:\n");
  GrafoTransposto(&Grafo, &Grafot);
  ImprimeGrafo(&Grafot);
  scanf("%*[^\n]");
  getchar();
  return 0;
}