// This code implements the Topological sort of a graph represented by
// its adjacency list. The file name should be taken as the first
// command line parameter.
//
// 1. Save this file as TopoSort.java
// 2. Compile it with javac TopoSort.java
// 3. Run with java TopoSort < dag.dat (or your own file name) 

import java.util.*;
import java.io.*;

public class TopoSort
{
  // this inner class describes a graph vertex 
  private static class Vertex 
  {
    String label;              // vertex label
    int color;                 // 0=white 1=gray 2=black
    int pred;                  // link to pred. in DFS forest
    int d;                     // discovery time
    int f;                     // finalizing time
    public Vertex(String label) // constructor
    {
      this.label = label;      // set up the vertex label
      pred = -1;
    }
  }
  private static Vertex[] vertices;  // array of graph vertices
  private static int[][] adjList;    // storage for adjacency list
  private static LinkedList<Vertex> sorted;  // results of sorting
  private static int time;           // global var needed for implementation

  public static void main(String[] args) throws IOException
  {
    readGraph();          // read graph encoding

    sorted = new LinkedList<Vertex>();
    DFS();                // compute vertex labels and predecessors
                          // and compose the linked list sorted

    // output of the vertex attributes 
    System.out.println("Result of sorting:");
    for (Iterator<Vertex> it=sorted.iterator(); it.hasNext(); )
    {
      Vertex v = it.next();
      System.out.println(v.label + " ");
    }
  }

  public static void DFS()   // main DFS method
  {
    time = 0;
    // color initialization (white) and vertex predecessors (nil) are
    // provided by the vertex object constructor
    for (int i=0; i<adjList.length; i++)
      if (vertices[i].color == 0)   // if color=white, explore the vertex
        DFS_Visit(i); 
  }

  public static void DFS_Visit(int i)
  {
    vertices[i].color = 1;                     // color v_i gray
    vertices[i].d = ++time;                    // discovery time
    
    for (int j=0; j<adjList[i].length; j++)
    {
      int ind = adjList[i][j];
      if (vertices[ind].color == 0)            // if color=white
      {
        vertices[ind].pred = i;
        DFS_Visit(ind);
      }
    }
 
    vertices[i].color = 2;                     // color v_i black  
    sorted.addFirst(vertices[i]);   //**** insert v_i in front of linked list 
    vertices[i].f = ++time;                    // finalizing time
  }

  // this method reads graph encoding from file
  public static void readGraph()
  {
    Scanner inFile = new Scanner(System.in);
  
    HashMap<String, Integer> nodeMap = 
       new HashMap<String, Integer>(); // storage for vertex labels
    ArrayList<Vertex> nodeList = 
       new ArrayList<Vertex>();        // storage for vertex objects
    String input = "";                 // storage for the entire file data
    int index = 0;
    while (inFile.hasNextLine())       // read all file records 
    {
      String s = inFile.nextLine();    // read a text line from file
      if (s.length() > 0 && s.charAt(0) != '#') // ignore comments
      {
        StringTokenizer sTk = new StringTokenizer(s);
        String label = sTk.nextToken(); // vertex label
        if (! nodeMap.containsKey(label)) // check for a new vertex in hash
        {
          Vertex v = new Vertex(label);   // create the vertex object
          nodeMap.put(label, new Integer(index)); // assign to it an index
          nodeList.add(v);                        // put it into node list
          index++;
          input = input + "#" + s;     // append the input line 
        }
        else                           // this vertex is already processed
        {
          System.out.println("Multiple declaration of vertex: " + label);
          System.exit(0);
        }
      }
    }
    inFile.close();                    // close input file

    // converting list into array
    vertices = (Vertex[]) nodeList.toArray(new Vertex[nodeList.size()]);

    // computing the adjacency list
    adjList = new int[vertices.length][];  // we already know # of vertices
    StringTokenizer sTk = new StringTokenizer(input, "#");
    for (int i=0; i<vertices.length; i++)
    {
      StringTokenizer sTk1 = new StringTokenizer(sTk.nextToken());
      adjList[i] = new int[sTk1.countTokens()-1];
      String s = sTk1.nextToken();
      for (int j=0; j<adjList[i].length; j++)
      {
        s = sTk1.nextToken();
        if (nodeMap.containsKey(s))
        {
          int ind = (nodeMap.get(s)).intValue();
          adjList[i][j] = ind;
        }
        else
        {
          System.out.println("Undeclared vertex: " + s);
          System.exit(0);
        } 
      }
    }
  }
}