CourseSchedule.java

package depth_first_search;

import java.util.*;

/**
 * Created by gouthamvidyapradhan on 22/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, is it possible for you to finish all courses?
 * <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 it is possible.
 * <p>
 * 2, [[1,0],[0,1]]
 * There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
 * <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.
 * <p>
 * Solution:
 * 1. Topologically sort the vertices.
 * 2. Pick each sorted vertex and mark each of its neighbours as visited,
 * if you encounter a vertex which is already visited then return false otherwise return true
 */
public class CourseSchedule {
    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}};
        System.out.println(new CourseSchedule().canFinish(2, pre));
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        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();

        while (!toposorted.isEmpty()) {
            int v = toposorted.poll();
            if (visited.get(v))
                return false;
            relax(v);
        }
        return true;
    }

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

}