Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.

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]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example: 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.

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.

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.

click to show more hints.

Hints:

This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort. Topological sort could also be done via BFS.

Solution

public class Solution {
   public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (prerequisites == null) {
            return false;
        }

        Map<Integer, Node> map = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            map.put(i, new Node(i));
        }

        for (int i = 0; i < prerequisites.length; i++) {
            int[] temp = prerequisites[i];
            Edge edge = new Edge(map.get(temp[0]), map.get(temp[1]));
            map.get(temp[0]).edgeList.add(edge);
            map.get(temp[1]).inboundValue = map.get(temp[1]).inboundValue + 1;
        }

        PriorityQueue<Node> priorityQueue = new PriorityQueue<>((n1, n2) -> {
            return Integer.compare(n1.inboundValue, n2.inboundValue);
        });

        for (Node n : map.values()) {
            priorityQueue.add(n);
        }


        int runner = 0;
        while (!priorityQueue.isEmpty()) {
            Node cur = priorityQueue.poll();
            if (cur.inboundValue != 0) {
                return false;
            }

            for (Edge e: cur.edgeList) {
                e.to.inboundValue --;
                priorityQueue.remove(e.to);
                priorityQueue.add(e.to);
            }

            runner ++;
        }

        if (runner == numCourses) {
            return true;
        } else {
            return false;
        }
    }


    public static class Node {
        int val;
        List<Edge> edgeList;
        int inboundValue;

        Node(int val) {
            this.val = val;
            edgeList = new ArrayList<>();
            inboundValue = 0;
        }
    }

    public static class Edge {
        Node from;
        Node to;

        Edge(Node from, Node to) {
            this.from = from;
            this.to = to;
        }
    }
}