// This code computes the strongly connected components of a graph represented 
// by the adjacency list. The file name should be taken as the first
// command line parameter.
//
// 1. Save this file as SCC.java
// 2. Compile it with javac SCC.java
// 3. Run with java SCC < scc.dat (or your own file name) 

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

public class SCC
{
  // this inner class describes a graph vertex 
  private static class Vertex 
  {
    String label;              // vertex label
    int color;                 // 0=white 1=gray 2=black
    int d;                     // discovery time
    int f;                     // finalizing time
    public Vertex(String label) // constructor
    {
      this.label = label;      // set up the vertex label
    }
  }
  private static Vertex[] vertices;  // array of graph vertices
  private static int[] vertexOrder;  // order of vertices in DFS
  private static int[][] adjList;    // storage for adjacency list
  private static int[][] adjListT;   // adj. list of G^T
  private static LinkedList<Integer> sorted = 
       new LinkedList<Integer>();    // results of sorting
  private static int time;           // global var needed for implementation

  public static void main(String[] args) throws IOException
  {
    readGraph();                     // read graph encoding
    printAdjList("Adjacency list of G", adjList);

  // STEP 1: calling DFS on G in the original order of vertices
    vertexOrder = new int[vertices.length];  // natural order of vertices
    System.out.println("\nNatural vertex order:");
    for (int i=0; i<vertices.length; i++)
    {
      vertexOrder[i] = i;
      System.out.print(vertices[i].label + " ");
    }

    System.out.println("\nCalling DFS on G:");
    DFS(adjList);         // compute vertex labels 

    System.out.println("DFS times:");
    for (int i=0; i<vertices.length; i++)
      System.out.println(vertices[i].label + ": " + vertices[i].d + "/" +
           vertices[i].f);


  // STEP 2: computing the adjacency list of G^T
    ArrayList<ArrayList<Integer>> al = 
        new ArrayList<ArrayList<Integer>>();    // create a 2-dim ArrayList
    for (int i=0; i<vertices.length; i++)
      al.add(new ArrayList<Integer>());
    for (int i=0; i<vertices.length; i++)       // transpose the adjList of G
      for (int j=0; j<adjList[i].length; j++)
         al.get(adjList[i][j]).add(new Integer(i));

    adjListT = new int[vertices.length][];      // converting list into array
    for (int i=0; i<vertices.length; i++)
    {
      adjListT[i] = new int[al.get(i).size()];
      int j=0;
      for (Iterator<Integer> it=al.get(i).iterator(); it.hasNext(); )
      {
        adjListT[i][j] = (it.next()).intValue();
        j++;
      }
    }
    printAdjList("\nAdjacency list of G^T", adjListT);


  // STEP 3: calling DFS on the graph G^T
      // reorder the vertices according to the f-values in decreasing order
    Iterator<Integer> it = sorted.iterator();
    for (int i=0; i<vertices.length; i++)
      vertexOrder[i] = (it.next()).intValue();

    System.out.println("\nVertex order according to the f-values:");
    for (int i=0; i<vertices.length; i++)
      System.out.print(vertices[vertexOrder[i]].label + "/" + 
                       vertices[vertexOrder[i]].f + " ");
    System.out.println();

    System.out.println("Calling DFS on G^T:");
    DFS(adjListT);

  // STEP 4: printing out the trees in the DFS forest
    // this is integrated in the DFS-related routines 
  }

  public static void DFS(int[][] adj) // main DFS method
  {
    for (int i=0; i<vertices.length; i++)
      vertices[i].color = 0;          // initialize color (white)
    time = 0;
    for (int i=0; i<adj.length; i++)
    {
      int ind = vertexOrder[i];       // index of the next vertex to process
      if (vertices[ind].color == 0)   // explore the vertex if it is white
      {
        System.out.print("Tree: ");   // root of the new DSF tree
        DFS_Visit(ind, adj);
        System.out.println();         // end of the current DFS tree listing
      }
    }
  }

  public static void DFS_Visit(int i, int[][] adj)
  {
    System.out.print(" " + vertices[i].label);
    vertices[i].color = 1;            // color v_i gray
    vertices[i].d = ++time;           // discovery time
    
    for (int j=0; j<adj[i].length; j++)
    {
      int ind = adj[i][j];
      if (vertices[ind].color == 0)   // if neighbor color=white
        DFS_Visit(ind, adj);          //   explore it
    }
 
    vertices[i].color = 2;            // color v_i black  
    sorted.addFirst(new Integer(i));  // insert in front of list           
    vertices[i].f = ++time;           // finalizing time
  }

  public static void printAdjList(String s, int[][] adj)
  {
    System.out.println(s);
    for (int i=0; i<adj.length; i++)
    {
      System.out.print(vertices[i].label + ": ");
      for (int j=0; j<adj[i].length; j++)
        System.out.print(vertices[adj[i][j]].label + " ");
      System.out.println();
    }
  }

  // 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);
        }
      }
    }

    // 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);
        } 
      }
    }
  }
}