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-ii/
 */
public class Problem210 {
    public int[] findOrder(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);
            }
        }
        boolean cycle = hasCycle(graph);
        if (cycle) {
            return new int[]{};
        }
        // TODO: topological sort
        return null;
    }

    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);
    }

    public static void main(String[] args) {
        Problem210 prob = new Problem210();
    }
}

@@ -351,21 +351,23 @@
 teger%3E%3E 
-graph
+adjList
  = new H
@@ -370,32 +370,81 @@
 ew HashMap%3C%3E();%0A
+        Set%3CInteger%3E vertices = new HashSet%3C%3E();%0A
         for (int
@@ -528,16 +528,93 @@
 tes%5Bi%5D;%0A
+            if (array.length != 2) %7B%0A                continue;%0A            %7D%0A
         
@@ -685,21 +685,23 @@
     if (
-graph
+adjList
 .contain
@@ -730,21 +730,23 @@
         
-graph
+adjList
 .get(fro
@@ -882,21 +882,23 @@
         
-graph
+adjList
 .put(fro
@@ -924,32 +924,118 @@
     %7D%0A        %7D%0A
+        for (int i = 0; i %3C numCourses; i++) %7B%0A            vertices.add(i);%0A        %7D%0A
         boolean 
@@ -1051,21 +1051,23 @@
 asCycle(
-graph
+adjList
 );%0A     
@@ -1136,53 +1136,1138 @@
     
-// TODO: topological sort%0A        return null
+List%3CInteger%3E path = topologicalSort(adjList, vertices);%0A        int%5B%5D result = new int%5Bpath.size()%5D;%0A        for (int i = 0; i %3C path.size(); i++) %7B%0A            result%5Bi%5D = path.get(i);%0A        %7D%0A        return result;%0A    %7D%0A%0A    private List%3CInteger%3E topologicalSort(Map%3CInteger, List%3CInteger%3E%3E adjList,%0A                                          Set%3CInteger%3E vertices) %7B%0A        Set%3CInteger%3E marked = new HashSet%3C%3E();%0A        List%3CInteger%3E path = new ArrayList%3C%3E();%0A        for (int vertex : vertices) %7B%0A            if (!marked.contains(vertex)) %7B%0A                topologicalSort(adjList, vertex, marked, path);%0A            %7D%0A        %7D%0A        return path;%0A    %7D%0A%0A    private void topologicalSort(Map%3CInteger, List%3CInteger%3E%3E adjList, int source,%0A                                 Set%3CInteger%3E marked, List%3CInteger%3E path) %7B%0A        marked.add(source);%0A        if (adjList.containsKey(source)) %7B%0A            for (int vertex : adjList.get(source)) %7B%0A                if (!marked.contains(vertex)) %7B%0A                    topologicalSort(adjList, vertex, marked, path);%0A                %7D%0A            %7D%0A        %7D%0A        path.add(source)
 ;%0A  
@@ -2729,35 +2729,40 @@
                 
-dfs
+hasCycle
 (graph, vertex, 
@@ -2942,19 +2942,24 @@
 te void 
-dfs
+hasCycle
 (Map%3CInt
@@ -2990,32 +2990,37 @@
 ph, int source,%0A
+     
                 
@@ -3076,16 +3076,21 @@
 marked,%0A
+     
         
@@ -3363,11 +3363,16 @@
     
-dfs
+hasCycle
 (gra
@@ -3599,103 +3599,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem210 prob = new Problem210();%0A    %7D
 %0A%7D%0A

Solve problem 210