// This program is written by Christopher Allsopp 


import java.util.*;

public class DiGraph {
    
    HashMap nodes = new HashMap(); // the graph of nodes
    
    class Node {
	
	private LinkedList neighbours; // node keys that this node points to
	private int indegree; // number of in edges
	private int resetValue; 
	// since we manipulate the indegree value we need to
	// be able to reset its original value after calling
	// loops() by storing it within the node object
	
	public Node() {
	    this.neighbours = new LinkedList ();
	    this.indegree = 0;
	    this.resetValue = this.indegree;
	} 
	
	void addNeighbour(Object key) {
	    this.neighbours.add(key);
	} 
	
	void removeNeighbour(Object key) {
	    this.neighbours.remove(key);	
	}
	
	void incrementIndegree() {
	    this.indegree++;
	}
	
	void decrementIndegree() {
	    this.indegree--;
	}
	
	LinkedList getNeighbours() {
	    return this.neighbours;
	}
	
	int getIndegree() {
	    return this.indegree;
	}
	
	boolean doesNeighbourExist(Object o) {
	    return this.neighbours.contains(o);
	}
	
	void printNeighbours() {
	    String str = neighbours.toString();
	    System.out.println(str.substring(1, str.length()-1));
	}
	
	void setResetValue() {
	    this.resetValue = this.indegree;
	}
	
	void resetIndegree() {
	    this.indegree = this.resetValue;
	}
	
    } // end inner class Node
    
    
    
    public DiGraph() {  // constructor	
    } // end constructor
    
    
    Node getNode(Object x) {
	return ((Node) nodes.get(x));	
    }
    
    
    public void addNode(Object x) {
	if (!containsNode(x)){
	    nodes.put(x, new Node());
	}
    } // end addNode
    
    
    public boolean removeNode(Object x) {
	    
	if (containsNode(x)) {
	    Object [] keys = nodes.keySet().toArray();
	    for (int i = 0; i < keys.length; i++) {
		removeEdge(getNode(keys[i]), x);
		// Note: removeEdge() checks to see if the edge exists before trying to delete it
	    }
	    nodes.remove(x);
	    return true;
	} else {
	    return false;
	}
    } // end removeNode
    
    
    public boolean containsNode(Object x) {
	return nodes.containsKey(x);
    } // end containsNode
    
    
    void addEdge(Object x, Object y) {
	
	addNode(x); 
	addNode(y);
	
	if (containsEdge(x,y)) { 
	    return;
	} else {
	    getNode(y).incrementIndegree();
	    getNode(x).addNeighbour(y);	
	}
	
    } // end addEdge
	
    
    boolean removeEdge(Object x, Object y) {
	
	if (containsEdge(x,y)) {
	    getNode(y).decrementIndegree();
	    getNode(x).removeNeighbour(y);
	    return true;
	} else {
	    return false;
	}
	
    } // end removeEdge
    
    
	
    boolean containsEdge(Object x, Object y) {
	
	if (containsNode(x) && containsNode(y)) {
	    return getNode(x).doesNeighbourExist(y);
	} else {
	    return false;
	}
    } // end containsEdge
    
    
    void print() {
	
	Object [] keys = nodes.keySet().toArray();
	Arrays.sort(keys);
	for (int i = 0; i < keys.length; i++) {
	    Object key = keys[i];
	    System.out.print(key + " --> ");
	    getNode(key).printNeighbours();
	}
    } // end print
    
	
    void enqueueZeroIndegreeNodes(Object [] keys, LinkedList ll) {
	// iterate through the graph and add all nodes with indegree(0) to the queue
	
	for (int i = 0; i < keys.length; i++) {
	    Object key = keys[i];
	    Node n = getNode(key);
	    n.setResetValue();
	    if(n.getIndegree() == 0) {
		ll.addLast(getNode(key)); //enqueue
	    }
	}
    } // end enqueueZeroIndegreeNodes
    
    
    void resetIndegrees(Object [] keys) {
	for (int i = 0; i < keys.length; i++) {
	    getNode(keys[i]).resetIndegree();
	}
    } // end resetIndegrees		 	  	
    
    
    
    boolean loops () {
	// return true if the graph contains a loop	
	
	Object [] keys = nodes.keySet().toArray();			
	LinkedList queue = new LinkedList();
		int deleteCount = 0; // we do not remove nodes so we need to keep track of
		// how many we have theoretically deleted
		
		//create intial queue
		enqueueZeroIndegreeNodes(keys, queue);
		
		while(!queue.isEmpty())	{
		    Node n = ((Node) queue.removeFirst()); // dequeue the first node
		    ListIterator li = n.getNeighbours().listIterator();
		    
		    // decrement all of the dequeued node's neighbours indegree count 
		    while (li.hasNext()) { 
			Node neighbour = ((Node) getNode(li.next()));
			neighbour.decrementIndegree();	
			
	 	        // enqueue the neighbour if its indegree count now equals zero
			if (neighbour.getIndegree() == 0) {
			    queue.addLast(neighbour); 
			}
			
	 	  	} // end inner while
		    
		    // in a normal topological sort, we remove the node from the graph here
		    deleteCount++; 
  	 	} // end outer while
	 	
	 	resetIndegrees(keys); 
		// if we 'deleted' all graph nodes, then graph is acyclic so return 'false'
	 	return (deleteCount != keys.length);
			
    } // end loops	
    

} // end DiGraph class