package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * https://leetcode.com/problems/course-schedule/
 */
public class Problem207 {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < prerequisites.length; i++) {
            int[] array = prerequisites[i];
            int from = array[0];
            int to = array[1];
            if (graph.containsKey(from)) {
                graph.get(from).add(to);
            } else {
                List<Integer> edges = new ArrayList<>();
                edges.add(to);
                graph.put(from, edges);
            }
        }
        return !hasCycle(graph);
    }

    private static class Cycle {
        boolean cycle;
    }

    private boolean hasCycle(Map<Integer, List<Integer>> graph) {
        Map<Integer, Boolean> onStack = new HashMap<>();
        Set<Integer> marked = new HashSet<>();
        Cycle cycle = new Cycle();
        for (int vertex : graph.keySet()) {
            onStack.put(vertex, false);
        }
        for (int vertex : graph.keySet()) {
            if (!marked.contains(vertex)) {
                dfs(graph, vertex, onStack, marked, cycle);
                if (cycle.cycle) {
                    return true;
                }
            }
        }
        return false;
    }

    private void dfs(Map<Integer, List<Integer>> graph, int source,
                     Map<Integer, Boolean> onStack, Set<Integer> marked,
                     Cycle cycle) {
        if (!graph.containsKey(source)) {
            return;
        }
        marked.add(source);
        onStack.put(source, true);
        for (int vertex : graph.get(source)) {
            if (!marked.contains(vertex)) {
                dfs(graph, vertex, onStack, marked, cycle);
            } else {
                if (onStack.get(vertex)) {
                    cycle.cycle = true;
                }
            }
        }
        onStack.put(source, false);
    }
}

@@ -61,107 +61,11 @@
 til.
-HashMap;%0Aimport java.util.HashSet;%0Aimport java.util.List;%0Aimport java.util.Map;%0Aimport java.util.Se
+Lis
 t;%0A%0A
@@ -230,59 +230,43 @@
     
-Map%3CInteger, List%3CInteger%3E%3E graph = new HashMap%3C%3E()
+List%5B%5D graph = new List%5BnumCourses%5D
 ;%0A  
@@ -291,29 +291,21 @@
  0; i %3C 
-prerequisites
+graph
 .length;
@@ -328,192 +328,36 @@
     
-int%5B%5D array = prerequisites%5Bi%5D;%0A            int from = array%5B0%5D;%0A            int to = array%5B1%5D;%0A            if (graph.containsKey(from)) %7B%0A                graph.get(from).add(to);%0A    
+graph%5Bi%5D = new ArrayList();%0A
     
@@ -353,39 +353,32 @@
 ist();%0A        %7D
- else %7B
 %0A               
@@ -374,91 +374,43 @@
     
-        List%3CInteger%3E edges = new ArrayList%3C%3E();%0A                edges.add(to);%0A   
+for (int%5B%5D preq : prerequisites) %7B%0A
     
@@ -421,255 +421,117 @@
     
- 
 graph
-.put(from, edges);%0A            %7D%0A        %7D%0A        return !hasCycle(graph
+%5Bpreq%5B1%5D%5D.add(preq%5B0%5D
 );%0A    
-%7D%0A%0A
     
-private static class Cycle %7B%0A        boolean cycle;%0A    %7D%0A%0A    private boolean hasCycle(Map%3CInteger, List%3CInteger%3E%3E graph) %7B%0A        Map%3CInteger, B
+%7D%0A        boolean%5B%5D visited = new boolean%5BnumCourses%5D;%0A        b
 oolean
-%3E
+%5B%5D
  onS
@@ -545,237 +545,102 @@
 new 
-HashMap%3C%3E();%0A        Set%3CInteger%3E marked = new HashSet%3C%3E();%0A        Cycle cycle = new Cycle();%0A        for (int vertex : graph.keySet()) %7B%0A            onStack.put(vertex, false);%0A        %7D%0A        for (int vertex : graph.keySet()
+boolean%5BnumCourses%5D;%0A        for (int i = 0; i %3C numCourses; i++) %7B%0A            if (visited%5Bi%5D
 ) %7B%0A
@@ -655,59 +655,61 @@
     
-if (!marked.
+    
 cont
-a
 in
-s(vertex)) %7B%0A                dfs
+ue;%0A            %7D%0A            if (!hasCycle
 (gra
@@ -705,37 +705,38 @@
 asCycle(graph, v
-ertex
+isited
 , onStack, marke
@@ -734,109 +734,43 @@
 ck, 
-marked, cycle);%0A                if (cycle.cycle) %7B%0A                    return true;%0A                %7D
+i)) %7B%0A                return false;
 %0A   
@@ -801,28 +801,27 @@
      return 
-fals
+tru
 e;%0A    %7D%0A%0A  
@@ -834,106 +834,74 @@
 ate 
-void dfs(Map%3CInteger, List%3CInteger%3E%3E graph, int source,%0A                     Map%3CInteger, B
+static boolean hasCycle(List%5B%5D graph, boolean%5B%5D visited, b
 oolean
-%3E
+%5B%5D
  onS
@@ -910,198 +910,113 @@
 ck, 
-Set%3CInteger%3E marked,%0A                     Cycle cycle) %7B%0A        if (!graph.containsKey(source)) %7B%0A            return;%0A        %7D%0A        marked.add(source);%0A        onStack.put(source,
+int n) %7B%0A        List%3CInteger%3E neighbors = graph%5Bn%5D;%0A        onStack%5Bn%5D = true;%0A        visited%5Bn%5D =
  true
-)
 ;%0A  
@@ -1034,78 +1034,56 @@
 int 
-vertex : graph.get(source)) %7B%0A            if (!marked.contains(vertex)
+adj : neighbors) %7B%0A            if (!visited%5Badj%5D
 ) %7B%0A
@@ -1102,11 +1102,21 @@
     
-dfs
+if (!hasCycle
 (gra
@@ -1120,21 +1120,22 @@
 graph, v
-ertex
+isited
 , onStac
@@ -1141,23 +1141,67 @@
 ck, 
-marked, cycle);
+adj)) %7B%0A                    return false;%0A                %7D
 %0A   
@@ -1249,20 +1249,13 @@
 tack
-.get(vertex)
+%5Badj%5D
 ) %7B%0A
@@ -1278,25 +1278,19 @@
     
-cycle.cycle = tru
+return fals
 e;%0A 
@@ -1349,27 +1349,40 @@
 tack
-.put(source, false)
+%5Bn%5D = false;%0A        return true
 ;%0A  

Update problem 207