CourseScheduleII.java

package depth_first_search;

import java.util.*;

/**
 * Created by gouthamvidyapradhan on 23/06/2017.
 * There are a total of n courses you have to take, labeled from 0 to n - 1.
 * <p>
 * Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
 * <p>
 * Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
 * <p>
 * There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
 * <p>
 * For example:
 * <p>
 * 2, [[1,0]]
 * There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]
 * <p>
 * 4, [[1,0],[2,0],[3,1],[3,2]]
 * There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].
 * <p>
 * Note:
 * The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
 * You may assume that there are no duplicate edges in the input prerequisites.
 */
public class CourseScheduleII {
    private Map<Integer, List<Integer>> graph;
    private BitSet visited;
    private Queue<Integer> toposorted;

    public static void main(String[] args) throws Exception {
        int[][] pre = {{1, 0}};
        int[] result = new CourseScheduleII().findOrder(2, pre);
        for (int i : result)
            System.out.print(i + " ");
        System.out.println();
    }

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int j = 0;
        int[] courses = new int[numCourses];
        int[] result = new int[numCourses];
        for (int i = 0; i < numCourses; i++)
            courses[i] = j++;
        graph = new HashMap<>();
        visited = new BitSet();
        toposorted = new ArrayDeque<>();
        //build graph
        for (int[] children : prerequisites) {
            graph.putIfAbsent(children[0], new ArrayList<>());
            graph.get(children[0]).add(children[1]);
        }
        graph.keySet().stream().filter(v -> !visited.get(v)).forEach(this::dfs);

        visited.clear();
        int i = 0;
        while (!toposorted.isEmpty()) {
            int v = toposorted.poll();
            if (visited.get(v))
                return new int[0];
            relax(v);
            result[i++] = v;
            courses[v] = -1;
        }
        //add the remaining courses
        for (int c : courses)
            if (c != -1)
                result[i++] = c;
        return result;
    }

    /**
     * Mark a vetex and its connected vertices as visited.
     *
     * @param v vertex
     */
    private void relax(int v) {
        visited.set(v);
        List<Integer> children = graph.get(v);
        if (children != null) {
            for (int c : children)
                visited.set(c);
        }
    }

    /**
     * Toposort
     *
     * @param v vertex
     */
    private void dfs(int v) {
        visited.set(v);
        List<Integer> children = graph.get(v);
        if (children != null) {
            for (int c : children)
                if (!visited.get(c))
                    dfs(c);
        }
        toposorted.offer(v);
    }
}