The general idea is as following: 1) Convert the Edge list format

graph to a Map<Vertex, List<Vertex>> format to provide efficient

access to adjacent nodes 2) Backtracking by using visiting set to

detect cycle More detailed description is in the comments.

```
/*
DSF on a Edge list format Graph is a nightmare (It s hard to find the adjacent nodes)
Convert it to Map<Vertex, List<Vertex>> format
*/
public class Solution {
private Map<Integer, List<Integer>> graph;
private Set<Integer> visited;
public boolean canFinish(int numCourses, int[][] prerequisites) {
graph = new HashMap<Integer, List<Integer>>();
visited = new HashSet<Integer>();
//build the Map<Vertex, List<Vertex>> format graph
for(int i=0; i<prerequisites.length; i++) {
int from = prerequisites[i][0];
int to = prerequisites[i][1];
if(graph.containsKey(from)) {
graph.get(from).add(to);
} else {
List<Integer> vertices = new ArrayList<Integer>();
vertices.add(to);
graph.put(from, vertices);
}
}
//Check every node that has not been visited yet.
for(Integer i : graph.keySet()) {
if(!visited.contains(i)) {
//create a new visiting set to detect potential cycle: you cannot 'visiting' a node twice in a acyclic graph
if(!detectCycle(i, new HashSet<Integer>()))
return false;
}
}
return true;
}
/*
@Param: from represents the node visiting from; visiting represent the current visiting path
@return boolean represent if there is a cycle
Backtracking the dfs because it is possible that a valid node being 'visiting' more than once.
no cycle but 7 will be 'visiting' twice
e.g. 1->7->0
1->2->7
*/
public boolean detectCycle(int from, Set<Integer> visiting) {
//Base Case: No adjacent Nodes -> return true
if(!graph.containsKey(from))
return true;
//DFS adjacent nodes
for(Integer to : graph.get(from)) {
if(visiting.contains(to))
return false;
else {
/*
The purpose of adding visited set is to avoid checking the same node multiple times
while the purpose of using visiting is to detect cycle.
*/
if(!visited.contains(to)) {
visiting.add(from);
visited.add(from);
if(!detectCycle(to, visiting))
return false;
visiting.remove(from);
}
}
}
return true;
}
}
```