Data Structures, Algorithms, & Applications in Java
Chapter 17, Exercise 35

First we input the number of vertices and edges in the new digraph; verify that these numbers are legitimate (i.e., neither is less than zero and the number of edges does not exceed the number of edges in a complete digraph with the given number of vertices); allocate an array h of the needed size; and finally read in the edges one by one. If each edge is added to the data structure being constructed using the method putEdge as we did in Exercise 31 for the establishment of an adjacency matrix structure, the time complexity becomes O(ne) because it takes O(n) time to verify that each edge is not already in the digraph.

We can reduce the complexity to O(n+e)) by deferring the check for duplicate edges to the end. Once the edges have been input, we can scan the adjacency list for each vertex using an array seen[0:n]. Initially, seen[v] is false for every vertex v. If vertex v is encountered on the adjacency list for vertex i, we first check to see if seen[v] is true. If it is, then we are seeing v for the second time on the adjacency list for vertex i. Therefore, we have found a duplicate edge and we throw a MyInputException exception. If seen[v] is false, then we are seeing v for the first time and we set seen[v] to true.

The code is given below. 
public class ExtendedLinkedWDigraph extends LinkedWDigraph
{
   // constructors
   public ExtendedLinkedWDigraph(int theVertices)
      {super(theVertices);}
   
   // default is a 0 vertex graph
   public ExtendedLinkedWDigraph()
      {super(0);}

   /** put edge e into the digraph, do not check if it is a duplicate */
   public void putEdgeNoCheck(Object theEdge)
   {
      WeightedEdge edge =  (WeightedEdge) theEdge;
      int v1 = edge.vertex1;
      int v2 = edge.vertex2;
      if (v1 < 1 || v2 < 1 || v1 > n || v2 > n || v1 == v2)
         throw new IllegalArgumentException
                   ("(" + v1 + "," + v2 + ") is not a permissible edge");

      // put v2 at front of chain aList[v1]
      aList[v1].add(0, new WeightedEdgeNode(v2, edge.weight));
      e++;
   }
   
   /** input a weighted digraph and store as this
     * @param inputMethod input method to use
     * @param inStream input stream for input */
   public void input(Method inputMethod, MyInputStream inStream)
   {
      // input number of vertices and edges
      System.out.println("Enter the number of vertices in the digraph");
      n = inStream.readInteger();
      if (n < 0)
         throw new MyInputException
                   ("number of vertices must be >= 0");

      System.out.println("Enter the number of edges in the digraph");
      int numOfEdges = inStream.readInteger();
      if (numOfEdges < 0)
         throw new MyInputException
                   ("number of edges must be >= 0");

      if (numOfEdges > n * (n - 1))
         throw new MyInputException("too many edges");

      // create a new array aList for the adjacency chains
      aList = new GraphChain [n + 1];
      for (int i = 1; i <= n; i++)
         aList[i] = new GraphChain();
      e = 0;    // reset current number of edges to zero
   
      // now input the edges and add them to a[][]
      WeightedEdge newEdge = new WeightedEdge(0, 0, null);
      Object [] inputMethodArgs = {inStream};
      for (int i = 1; i <= numOfEdges; i++)
      {
         System.out.println("Enter edge " + i);
         newEdge.vertex1 = inStream.readInteger();
         newEdge.vertex2 = inStream.readInteger();
         try
         {
            newEdge.weight = 
               (Operable) inputMethod.invoke(null, inputMethodArgs);
         }
         catch (Exception e)
         {
            throw new IllegalArgumentException
                      ("static method input() not defined");
         }
         putEdgeNoCheck(newEdge);
      }

      // check for duplicate edges
      boolean [] seen = new boolean [n + 1];
      for (int i = 1; i <= n; i++)
      {// check vertex i
         Iterator ig = iterator(i);
         while (ig.hasNext())
         {// not at list end 
            int v = ((WeightedEdgeNode) ig.next()).vertex;
            if (seen[v])
               // duplicate edge
               throw new MyInputException
                         ("Duplicate edges encountered in input");
            else seen[v] = true;
         }
   
         // reset seen
         ig = iterator(i);  
         while (ig.hasNext())
            // not at list end 
            seen[((WeightedEdgeNode) ig.next()).vertex] = false;
      }
   }
}