import java.util.*;
import java.util.concurrent.CopyOnWriteArrayList;

public class GraphDetectCycleAndRemove {
	
	static class DirectedGraphNode { 
		int label; 
		List<DirectedGraphNode> neighbors ;		
		
		//constructor, Time O(1), Space O(1)
		DirectedGraphNode(int  x) { 
			label = x; 
			neighbors =  new CopyOnWriteArrayList<>();	
		} 
		
	    public String toString() {	    	
	    	return String.valueOf(label);
	    }
	} 
	
	//adjacency list
	Map<Integer, DirectedGraphNode> adj = new HashMap<>();

	//Add nodes and edges, Time O(1), Space O(1)
	public void addEdge(int a, int b) {
		adj.putIfAbsent(a, new DirectedGraphNode(a));
		adj.putIfAbsent(b, new DirectedGraphNode(b));
		DirectedGraphNode node1 = adj.get(a);
		DirectedGraphNode node2 = adj.get(b);
		node1.neighbors.add(node2); //add edge		
	}

	//Detect whether there is cycle in graph, DFS, Time O(V+E), Space O(V)
	public boolean detectCycle() {
	    Map<Integer, Boolean> visited = new HashMap<>();
	    Map<Integer, Boolean> backTrack = new HashMap<>();
 	 	for (int key: adj.keySet()) {
	    	visited.put(key, false);
	    	backTrack.put(key, false);
 	 	}
	    for (Integer key: adj.keySet()) {	
	        if (!visited.get(key)) {
	            if (cycleUtil(key, visited, backTrack,0)) {                
	                return true;
	            }   
	        }
	    }
	    
	    return false;
	}
	
	//DFS helper, Recursion + memoization, Time O(V+E), Space O(V)
	private boolean cycleUtil(int v,  Map<Integer, Boolean> visited, Map<Integer, Boolean> backTrack, int level) {
		if (backTrack.get(v)) 
    		return true;   
	    if (visited.get(v))
	    	return false;	    
	    visited.put(v, true);
	    backTrack.put(v, true);;
	    for (DirectedGraphNode ne : adj.get(v).neighbors) {
           if (cycleUtil(ne.label, visited, backTrack, level+1))
                return true; 
	    }
	    backTrack.put(v, false);	   
	    return false;
	}
	
	//Check all edges, remove one edge at a time and check whether the cycle is removed
	//Time O(E*(V+E)), Space O(V)
	public boolean removeCycle() {
		for (int key: adj.keySet()) {
			for (DirectedGraphNode ne: adj.get(key).neighbors) {
				removeEdge(key, ne.label);
				boolean b = detectCycle();
				if (!b) {//no more cycle
					System.out.println("remove edge: "+ key+","+ne);
					return true;				
				}
				else 
					addEdge(key, ne.label); //add back
			}
		}
		return false;
	}
	
	//Remove edges, Time O(1), Space O(1)
	public void removeEdge(int a, int b) {
		DirectedGraphNode node1 = adj.get(a);
		DirectedGraphNode node2 = adj.get(b);
		if (node1 == null || node2 == null)
			return;
		node1.neighbors.remove(node2);
	}

	public static void main(String a[])	{	
		//build directed graph with one cycle
		/*
		 *      1
		 *    > |
		 *   /  V
		 * 0 <- 2 
		 *      |
		 *      V
		 *      3
		 */
		GraphDetectCycleAndRemove g = new GraphDetectCycleAndRemove();
		g.addEdge(0, 1);
		g.addEdge(1, 2);
		g.addEdge(2, 0);	
		g.addEdge(2, 3);	
		
		boolean hasCycle = g.detectCycle();
		System.out.println("has cycle: " + hasCycle);		
		if (hasCycle)
			g.removeCycle();
		hasCycle = g.detectCycle();
		System.out.println("After remove, has cycle: " + hasCycle);
	}
}