207. 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:

  1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  2. You may assume that there are no duplicate edges in the input prerequisites.

click to show more hints.

Hints:

  1. 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.
  2. Topological Sort via DFS – A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
  3. Topological sort could also be done via BFS.
public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, Set<Integer>> inDegree = new HashMap<>();
        Map<Integer, Set<Integer>> outDegree = new HashMap<>();
        Set<Integer> set = new HashSet<>();

        // Init courses
        for (int i = 0; i < numCourses; i++) {
            inDegree.put(i, new HashSet<>());
            outDegree.put(i, new HashSet<>());
            set.add(i);
        }

        // Parse course prerequisites
        for (int i = 0; i < prerequisites.length; i++) {
            int current = prerequisites[i][0];
            int pre = prerequisites[i][1];

            inDegree.get(current).add(pre);
            outDegree.get(pre).add(current);
        }

        Queue<Integer> queue = new LinkedList<>();
        for (Integer course : set) {
            if (inDegree.get(course).size() == 0) {
                queue.add(course);
            }
        }

        int index = 0;
        int[] result = new int[set.size()];
        while (!queue.isEmpty()) {
            Integer course = queue.poll();
            result[index++] = course;
            for (Integer next : outDegree.get(course)) {
                inDegree.get(next).remove(course);
                if (inDegree.get(next).size() == 0) {
                    queue.offer(next);
                }
            }
        }

        if (index != set.size()) {
            return false;
        } else {
            return true;
        }
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s