https://leetcode.com/problems/course-schedule/

Whether is possible to finish all the course depends on whether there is a circle prerequisites in the course list.
Hence, we only need to compute if there is a topological ordering of the courses.

Steps of the algorithm (BFS):

  1. Find vertices with in-degree of 0, put them into a queue
  2. While queue is not empty, poll the queue, find the vertices which are pointed by the vertices we just polled from the queue
  3. If there is no vertex left in the graph, then there is a valid topological ordering

From Wikipedia: a BFS method

1
2
3
4
5
6
7
8
9
10
11
12
13
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)

My code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegrees = new int[numCourses]; // how many pre for course[i]
        for (int[] pair : prerequisites) {
            indegrees[pair[0]]++; 
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < indegrees.length; i++) {
            if (indegrees[i] == 0) {
                q.offer(i);
            }
        }
        int count = q.size();
        while (!q.isEmpty()) {
            int i = q.poll();
            for (int[] pair : prerequisites) {
                if (pair[1] == i) {
                    indegrees[pair[0]]--;
                    if (indegrees[pair[0]] == 0) { 
                        q.offer(pair[0]);
                        count++;
                    }
                }
            }
        }
        return count == numCourses;
    }
}

The running time is O(v^2) since the while loop is O(V) and there is a for loop for O(V) inside.
We can improve the speed by building a adjacent list for the neighbor of vertex.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegrees = new int[numCourses]; // how many pre for course[i]
        List<Integer>[] adj = new ArrayList[numCourses];
        for (int[] pair : prerequisites) {
            int pre = pair[1], cur = pair[0];
            if (adj[pre] == null) {
                adj[pre] = new ArrayList<>();
            }
            List<Integer> list = adj[pre];
            list.add(cur);
            indegrees[cur]++; 
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < indegrees.length; i++) {
            if (indegrees[i] == 0) {
                q.offer(i);
            }
        }
        int count = 0;
        while (!q.isEmpty()) {
            int i = q.poll();
            count++;
            if (adj[i] != null) {
                for (Integer neibor : adj[i]) {
                    indegrees[neibor]--;
                    if (indegrees[neibor] == 0) {
                        q.offer(neibor);
                    }
                }
            }
        }
        return count == numCourses;
    }
}