Find whether it is possible to finish all tasks or not from given dependencies

The problem, simply

There are numCourses tasks numbered 0 to numCourses - 1. Each pair [a, b] means task b must be done before task a.

Return true if you can finish every task in some order, and false if the rules make that impossible. Here V is the number of tasks and E the number of pairs.

A story to remember it

Picture it

Examples

Way 1: the simple way

Walk around the room again and again. Each time, look for any task that is not done and whose "before" tasks are all done. Do it. If a full trip around finds nothing to do while tasks remain, you are stuck.

1. For each task, keep the list of tasks it needs.
2. Repeat: scan all tasks. Do the first one that is not done and has all its needs done.
3. If a scan does nothing, return whether every task is done.

class TasksRepeatedScan {
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> needs = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) needs.add(new ArrayList<>());
        for (int[] p : prerequisites) needs.get(p[0]).add(p[1]);   // p[0] needs p[1]

        boolean[] done = new boolean[numCourses];
        int doneCount = 0;
        boolean progress = true;
        while (progress) {
            progress = false;
            for (int t = 0; t < numCourses; t++) {                // one trip around the room
                if (done[t]) continue;
                boolean ready = true;
                for (int b : needs.get(t)) if (!done[b]) { ready = false; break; }
                if (ready) { done[t] = true; doneCount++; progress = true; }
            }
        }
        return doneCount == numCourses;
    }
}

How long it takes: every trip costs O(V + E), and each useful trip finishes at least one task, so up to V trips: O(V * (V + E)). Extra room: the need lists, O(V + E).

Way 2: the clever way

Do not rescan. Keep a count of how many tasks each task still waits for, and a ready line, a queue, of tasks that wait for nothing. When a task is done, only the tasks waiting for it can change, so only look at those.

1. For each pair [a, b], add an arrow b to a and add 1 to waits[a].
2. Put every task with waits == 0 in the ready line.
3. Take a task out, count it as done, and lower waits for every task it points to. Any that reach 0 join the line.
4. At the end, return done == numCourses.

class TasksKahn {
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> after = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) after.add(new ArrayList<>());
        int[] waits = new int[numCourses];
        for (int[] p : prerequisites) {
            after.get(p[1]).add(p[0]);          // p[1] must happen before p[0]
            waits[p[0]]++;
        }
        Deque<Integer> ready = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) if (waits[i] == 0) ready.add(i);

        int done = 0;
        while (!ready.isEmpty()) {
            int t = ready.poll();
            done++;
            for (int next : after.get(t)) {
                if (--waits[next] == 0) ready.add(next);   // its last need was just done
            }
        }
        return done == numCourses;              // anything left is stuck in a circle
    }

    public static void main(String[] args) {
        System.out.println(canFinish(6, new int[][]{{1, 0}, {2, 0}, {3, 1}, {3, 2}, {4, 2}, {5, 3}, {5, 4}}));  // true
        System.out.println(canFinish(2, new int[][]{{1, 0}, {0, 1}}));                                          // false
    }
}

How long it takes: every task joins the line once and every arrow is crossed off once, O(V + E). Extra room: the arrow lists O(V + E) and the counts and line O(V).

Another way: look for a circle with depth first search

The tasks can all be done exactly when the arrows have no circle. So walk the arrows with three states: not started, on the current walk, and finished. An arrow into a task that is on the current walk is a circle.

class TasksDfs {
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> after = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) after.add(new ArrayList<>());
        for (int[] p : prerequisites) after.get(p[1]).add(p[0]);
        int[] state = new int[numCourses];      // 0 new, 1 on the walk, 2 finished
        for (int i = 0; i < numCourses; i++) {
            if (state[i] == 0 && hasCircle(i, after, state)) return false;
        }
        return true;
    }

    static boolean hasCircle(int u, List<List<Integer>> after, int[] state) {
        state[u] = 1;
        for (int v : after.get(u)) {
            if (state[v] == 1) return true;
            if (state[v] == 0 && hasCircle(v, after, state)) return true;
        }
        state[u] = 2;
        return false;
    }
}

Also O(V + E) time and O(V + E) room. The recursion can be V calls deep, which is the main reason many people prefer the queue version.

Watch out for

• Return done == numCourses, not "the line became empty". The line always empties in the end.
• A task that needs itself, [0, 0], is a circle of one. Kahn's way handles it: task 0 waits for 1 thing forever.
• Repeated pairs add to waits twice and also add the arrow twice, so they cancel out correctly. Do not remove repeats from only one side.

What interviewers ask next

• Return an order of tasks, not only true or false (Course Schedule II): record the order in which tasks leave the line. If it has fewer than numCourses tasks, return an empty list.
• Fewest semesters if any number of ready tasks can run at once: process the line level by level, and count levels.
• Fewest semesters with at most k tasks per semester: this becomes a bitmask search, much harder.
• Is there exactly one valid order? Only if the line never holds more than one task at a time.
• How would you find which tasks are in a circle? With DFS, keep parents and walk back when you hit an "on the walk" task.

Remember this

Grown-up words: tasks are vertices, "before" rules are directed edges, the waiting count is the in-degree, the ready line is a queue, the finished order is a topological order, this method is Kahn's algorithm, and a circle of rules is a cycle in a directed graph.