package graph;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

class PostOrder<V> {
  
  private final Graph<V> g;
  private final HashSet<V> visited;
  private final LinkedList<V> list;

  PostOrder(Graph<V> g) {
    this.g = g;
    this.visited = new HashSet<V>();
    this.list = new LinkedList<V>();
    for (V v : this.g.vertices())
      dfs(v);
  }
  
  void dfs(V v) {
    if (this.visited.contains(v)) return;
    this.visited.add(v);
    for (V w : this.g.successors(v))
      dfs(w);
    this.list.addFirst(v);
  }

  List<V> order() {
    return this.list;
  }
  
}

class TestPostOrder {
  public static void main(String[] args) {
    Graph<Integer> g = new Graph<Integer>();
    int[][] edges = new int[][] { {0,3}, {1,0}, {1,4}, {2,4}, {2, 5},
        {3,1}, {4,3} };
    for (int v = 0; v <= 5; v++)
      g.addVertex(v);
    for (int[] e: edges)
      g.addEdge(e[0], e[1]);
    PostOrder<Integer> po = new PostOrder<>(g);
    System.out.println(po.order());
  }

}