public boolean canFinish(int numCourses, int[][] prerequisites) {

Map<Integer, Set<Integer>> graph = initGraph(prerequisites);

Set<Integer> visited = new HashSet<>();

for (int i=0; i<numCourses; i++) {

if (graph.containsKey(i) && !visited.contains(i) && !dfs(graph, visited, new HashSet<>(), i)) return false;

}

return true;

}

private boolean dfs(Map<Integer, Set<Integer>> graph, Set<Integer> visited, Set<Integer> onStack, Integer pre) {

if (onStack.contains(pre)) return false;

visited.add(pre);

onStack.add(pre);

if (!graph.containsKey(pre)) return true;

Set<Integer> adj = graph.get(pre);

for (Integer curr: adj) {

if (graph.containsKey(curr) && !dfs(graph, visited, onStack, curr)) return false;

}

onStack.remove(pre);

return true;

}

private Map<Integer, Set<Integer>> initGraph(int[][] prerequisites) {

Map<Integer, Set<Integer>> graph = new HashMap<>();

for (int[] p: prerequisites) {

addEdge(graph, p);

}

return graph;

}

private void addEdge(Map<Integer, Set<Integer>> graph, int[] p) {

Set<Integer> adj = graph.getOrDefault(p[1], new HashSet<>());

adj.add(p[0]);

graph.put(p[1], adj);

}

/**

public boolean canFinish2s(int numCourses, int[][] prerequisites) {

ArrayList[] graph = new ArrayList[numCourses];

int[] degree = new int[numCourses];

Queue queue = new LinkedList();

int count=0;

for(int i=0;i<numCourses;i++)

graph[i] = new ArrayList();

for(int i=0; i<prerequisites.length;i++){

degree[prerequisites[i][1]]++;

graph[prerequisites[i][0]].add(prerequisites[i][1]);

}

for(int i=0; i<degree.length;i++){

if(degree[i] == 0){

queue.add(i);

count++;

}

}

while(queue.size() != 0){

int course = (int)queue.poll();

for(int i=0; i<graph[course].size();i++){

int pointer = (int)graph[course].get(i);

degree[pointer]--;

if(degree[pointer] == 0){

queue.add(pointer);

count++;

}

}

}

if(count == numCourses)

return true;

else

return false;

}

/**

public boolean canFinish3(int numCourses, int[][] prerequisites) {

int[] indegree = new int[numCourses];

Set<Integer>[] graph = new Set[numCourses];

for (int[] link: prerequisites) {

if (graph[link[1]] == null) graph[link[1]] = new HashSet<Integer>();

graph[link[1]].add(link[0]);

indegree[link[0]]++;

}

Queue<Integer> q = new LinkedList<>();

for (int i=0; i<numCourses; i++) {

if (indegree[i] == 0) q.add(i);

}

int count = 0;

while (!q.isEmpty()) {

int curr = q.poll();

if (graph[curr] == null) {

count++;

continue;

}

for (int next: graph[curr]) {

indegree[next]--;

if (indegree[next] == 0) q.add(next);

}

count++;

}

return count == numCourses;

}

public boolean canFinish4(int numCourses, int[][] prerequisites) {

Set<Integer>[] graph = new Set[numCourses];

for (int[] link: prerequisites) {

if (graph[link[1]] == null) graph[link[1]] = new HashSet<Integer>();

graph[link[1]].add(link[0]);

}

return !isCyclic(graph, numCourses);

}

private boolean isCyclic(Set<Integer>[] graph, int numCourses) {

boolean[] visited = new boolean[numCourses];

boolean[] trace = new boolean[numCourses];

for (int i=0; i<numCourses; i++) {

if (isCyclic(graph, i, visited, trace)) return true;

}

return false;

}

private boolean isCyclic(Set<Integer>[] graph, int start, boolean[] visited, boolean[] trace) {

if (trace[start]) return true;

if (visited[start]) return false;

visited[start] = true;

if (graph[start] == null) return false;

trace[start] = true;

for (int next: graph[start]) {

if (isCyclic(graph, next, visited, trace)) return true;

}

trace[start] = false;

return false;

}