#include <stdio.h>
#include <stdlib.h>
#define MAXNUMVERTICES  100
#define MAXNUMARESTAS   100

typedef long TipoPeso;
typedef int TipoVertice;
typedef struct TipoGrafo {
  TipoPeso Mat[MAXNUMVERTICES + 1][MAXNUMVERTICES + 1];
  int NumVertices;
  int NumArestas;
} TipoGrafo;

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

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

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

void Visita(long k, TipoGrafo * Grafo, long * Tempo, long * d)
{ long j;
  (*Tempo)++;
  d[k] = *Tempo;
  for (j = 0; j < Grafo->NumVertices; j++) 
    { if (Grafo->Mat[k][j] > 0) 
        if (d[j] == 0) 
        { printf(" Visita:%2ld", j);
          Visita(j, Grafo, Tempo, d);
        }
    }
  printf("\n Desmarcando vertice:%2ld\n", k);
  *Tempo--;  d[k] = 0;
}

void Dfs(TipoGrafo * Grafo)
{ long Tempo,i, d[MAXNUMVERTICES + 1];
  Tempo = 0;
  for (i = 0; i < Grafo->NumVertices; i++) d[i] = 0;
  i = 0;
  printf(" Raiz:%2ld\n", i);
  Visita(i, Grafo, &Tempo, d);
}


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