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

#define MAXNUMVERTICES  100
#define MAXNUMARESTAS   4500
#define TRUE            1
#define FALSE           0
#define MAXTAM          (MAXNUMVERTICES + MAXNUMARESTAS * 2)

typedef int TipoValorVertice;
typedef int TipoPeso;
typedef int  TipoTam;
typedef struct TipoGrafo {
  TipoTam Cab[MAXTAM + 1];
  TipoTam Prox[MAXTAM + 1];
  TipoTam Peso[MAXTAM + 1];
  TipoTam ProxDisponivel;
  char NumVertices;
  short NumArestas;
} TipoGrafo;
typedef short TipoApontador;

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

void FGVazio(TipoGrafo *Grafo)
{ short i;
  for (i = 0; i <= Grafo->NumVertices; i++) 
    { Grafo->Prox[i] = 0;  Grafo->Cab[i] = i;
      Grafo->ProxDisponivel = Grafo->NumVertices;
    }
}

void InsereAresta(TipoValorVertice *V1, TipoValorVertice *V2,
                  TipoPeso *Peso, TipoGrafo *Grafo)
{ short Pos;
  Pos = Grafo->ProxDisponivel;
  if (Grafo->ProxDisponivel == MAXTAM) 
  { printf("nao ha espaco disponivel para a aresta\n"); return;
  }
  Grafo->ProxDisponivel++;  Grafo->Prox[Grafo->Cab[*V1]] = Pos;
  Grafo->Cab[Pos] = *V2;  Grafo->Cab[*V1] = Pos;
  Grafo->Prox[Pos] = 0;  Grafo->Peso[Pos] = *Peso;
}

short ExisteAresta(TipoValorVertice Vertice1,
                   TipoValorVertice Vertice2, TipoGrafo *Grafo)
{ TipoApontador Aux;
  short EncontrouAresta = FALSE;
  Aux = Grafo->Prox[Vertice1];
  while (Aux != 0 && EncontrouAresta == FALSE) 
    { if (Vertice2 == Grafo->Cab[Aux]) EncontrouAresta = TRUE;
      Aux = Grafo->Prox[Aux];
    }
  return EncontrouAresta;
}  

/* Operadores para obter a lista de adjacentes */
short ListaAdjVazia(TipoValorVertice *Vertice, TipoGrafo *Grafo)
{ return (Grafo->Prox[*Vertice] == 0); } 

TipoApontador PrimeiroListaAdj(TipoValorVertice *Vertice, 
                               TipoGrafo *Grafo)
{ return (Grafo->Prox[*Vertice]); } 

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

void RetiraAresta(TipoValorVertice *V1, TipoValorVertice *V2,
                  TipoPeso *Peso, TipoGrafo *Grafo)
{ TipoApontador Aux, AuxAnterior;  short EncontrouAresta = FALSE;
  AuxAnterior = *V1;  Aux = Grafo->Prox[*V1];
  while (Aux != 0 && EncontrouAresta == FALSE) 
    { if (*V2 == Grafo->Cab[Aux]) EncontrouAresta = TRUE;
      else { AuxAnterior = Aux; Aux = Grafo->Prox[Aux]; }
    }
  if (EncontrouAresta) /* Apenas marca como retirado */
  { Grafo->Cab[Aux] = MAXNUMVERTICES + MAXNUMARESTAS * 2;
  } 
  else printf("Aresta nao existe\n");
} 
void LiberaGrafo(TipoGrafo *Grafo)
{  /* Nao faz nada no caso de posicoes contiguas */ } 

void ImprimeGrafo(TipoGrafo *Grafo)
{ short i, forlim;
  printf("    Cab Prox Peso\n");
  forlim = Grafo->NumVertices + Grafo->NumArestas * 2;
  for (i = 0; i <= forlim - 1; i++)
    printf("%2d%4d%4d%4d\n", i, Grafo->Cab[i], 
           Grafo->Prox[i], Grafo->Peso[i]);
} 

void GrafoTransposto(TipoGrafo *Grafo, TipoGrafo *GrafoT)
{ TipoValorVertice v, Adj;
  TipoPeso Peso; TipoApontador Aux;
  GrafoT->NumVertices = Grafo->NumVertices;
  GrafoT->NumArestas = Grafo->NumArestas;
  FGVazio(GrafoT);
  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 --*/
  /* -- NumVertices: definido antes da leitura das arestas --*/
  /* -- NumArestas: inicializado com zero e incrementado a --*/
  /* -- cada chamada de InsereAresta                       --*/
  printf("No. vertices:");
  scanf("%d%*[^\n]", &NVertices);
  getchar();
  printf("No. arestas:");
  scanf("%hd%*[^\n]", &NArestas);
  getchar();
  Grafo.NumVertices = NVertices;
  Grafo.NumArestas = 0;
  FGVazio(&Grafo);

  for (i = 0; i <= NArestas - 1; i++) 
  { printf("Insere V1 -- V2 -- Peso:");
    scanf("%d%d%d%*[^\n]", &V1, &V2, &Peso);
    getchar();
    Grafo.NumArestas++;
    InsereAresta(&V1, &V2, &Peso, &Grafo);   /* 1 chamada g-direcionado    */
    /*InsereAresta(V2, V1, Peso, Grafo);*/
    /* 2 chamadas g-naodirecionado*/
  }
  ImprimeGrafo(&Grafo);
  scanf("%*[^\n]");
  getchar();
  GrafoTransposto(&Grafo, &GrafoT);
  ImprimeGrafo(&GrafoT);
  scanf("%*[^\n]");
  getchar();
  printf("Insere V1 -- V2 -- Peso:");
  scanf("%d%d%d%*[^\n]", &V1, &V2, &Peso);
  getchar();
  if (ExisteAresta(V1, V2, &Grafo))
  printf("Aresta ja existe\n");
  else 
  { Grafo.NumArestas++;
    InsereAresta(&V1, &V2, &Peso, &Grafo);
    /*InsereAresta(V2, V1, Peso, Grafo);*/
  }
  ImprimeGrafo(&Grafo);
  scanf("%*[^\n]");
  getchar();
  printf("Lista adjacentes de: ");
  scanf("%d", &V1);
  if (!ListaAdjVazia(&V1, &Grafo)) 
  { Aux = PrimeiroListaAdj(&V1, &Grafo);
    FimListaAdj = FALSE;
    while (!FimListaAdj) 
      { ProxAdj(&V1, &Grafo, &Adj, &Peso, &Aux, &FimListaAdj);
        printf("%2d (%d)", Adj, Peso);
      }
    putchar('\n');
    scanf("%*[^\n]");
    getchar();
  }
  printf("Retira aresta V1 -- V2:");
  scanf("%d%d%*[^\n]", &V1, &V2);
  getchar();
  if (ExisteAresta(V1, V2, &Grafo)) 
  { Grafo.NumArestas--;
    RetiraAresta(&V1, &V2, &Peso, &Grafo);
    /*RetiraAresta(V2, V1, Peso, Grafo);*/ /* grafo nao e dirigido */
  } 
  else printf("Aresta nao existe\n");
  ImprimeGrafo(&Grafo);
  scanf("%*[^\n]");
  getchar();
  printf("Existe aresta V1 -- V2:");
  scanf("%d%d%*[^\n]", &V1, &V2);
  getchar();
  if (ExisteAresta(V1, V2, &Grafo)) printf(" Sim\n");
  else printf(" Nao\n");
  LiberaGrafo(&Grafo);   /* Imprime sujeira normalmente */
  ImprimeGrafo(&Grafo);
  return 0;
}