Maximum Completable Tasks with Prerequisites (Topological)

Requirements

Given a collection of tasks, where every task is associated with a possibly empty list of prerequisite tasks, determine how many tasks are completable.

A task may be completed only when each of its prerequisites is completable and the task is not contained in, nor dependent on, a cycle. A cycle includes every task in a strongly connected component containing more than one task. Any task that eventually relies on such a component is also uncompletable.

Implement:

def count_completable_tasks(prerequisites: list[list[int]]) -> int:
    pass

Here, prerequisites[i] lists the tasks that must be completed before task i, and the return value is the number of tasks that can ultimately be completed.

Examples

Example 1

Input:  [[ ], [0], [1], [0]]
Output: 4

Task 0 has no prerequisites, task 1 follows 0, task 2 follows 1, and task 3 follows 0; therefore every task can be completed.

Example 2

Input:  [[2], [0], [1], []]
Output: 1

Tasks 0, 1, and 2 form a cycle, so only independent task 3 is completable.

Example 3

Input:  [[0], []]
Output: 1

Task 0 has a self-dependency and is invalid, while task 1 has no prerequisites and can be completed.

Notes

• Tasks with no prerequisites are immediately eligible for completion.
• A task that depends on a cyclic group is not completable, even if the task itself is not part of the cycle.
• The required result is the integer count of completable tasks, not a completion ordering or a Boolean indicating whether every task is feasible.
• Confirm the required input and output interface before implementation, since equivalent versions of this problem may request a count, a Boolean, or an ordered completion list.

Constraints

• There are V tasks, indexed from 0 through V - 1.
• Each prerequisite reference identifies a task in that range.
• A prerequisite list may be empty.
• The expected target complexity is linear in the graph size: O(V + E) time and O(V + E) space, where E is the number of prerequisite relationships.