/******************************GraphTraverse.java******************************/
import java.util.*;

public class GraphTraverse  { 

  static int id;                           // Variable zum Numerieren
  
  public static void tiefensuche(Graph g){
    id = 0;                                // Initialisiere Zaehler
    for (Vertex v : g.vertices())          // fuer jeden Knoten
      v.seen = false;                      // markiere als nicht besucht
    for (Vertex v : g.vertices())          // fuer jeden Knoten
      if (!v.seen) visit(v);               // falls v nicht besucht: besuche v
  }

  private static void visit(Vertex v) {
    v.nr   = id++;                         // vergib naechste Nummer
    v.seen = true ;                        // markiere als besucht
    for (Edge e : v.edges){                // fuer jede ausgehende Kante
      Vertex w = e.dest;                   // sei w der Nachbarknoten
      if (!w.seen) visit(w);               // falls w nicht besucht: besuche w
    }
  }
}