Task Dependency Validator

Medium

You are given a project management system that needs to schedule numTasks tasks, labeled from 0 to numTasks - 1 . Some tasks have prerequisite requirements that must be satisfied before they can begin execution. You are provided with an array dependencies where each element dependencies[i] = [taskᵢ, requiredTaskᵢ] indicates that requiredTaskᵢ must be completed before taskᵢ can start. In other words, there is a directed dependency from requiredTaskᵢ to taskᵢ . For example, the dependency [3, 1] means that task 1 must be finished before task 3 can begin. Your goal is to determine whether it is possible to complete all tasks given these dependency constraints. If the dependencies form a valid execution order (no circular dependencies exist), return true . Otherwise, if there exists a cycle in the dependencies that makes it impossible to complete all tasks, return false . This is fundamentally a cycle detection problem in a directed graph, where tasks are nodes and dependencies are directed edges. The problem can be solved using: Depth-First Search (DFS) with three-color marking to detect back edges Breadth-First Search (BFS) using Kahn's algorithm for topological sorting Topological Sort verification - if a valid topological order exists, there are no cycles The key insight is that a valid task ordering exists if and only if the dependency graph is a Directed Acyclic Graph (DAG) . Any cycle in the graph means there's a mutual dependency that cannot be resolved, making it impossible to complete all tasks.

Example 1

Input

numTasks = 2
dependencies = [[1,0]]

Output

true

Explanation

There are 2 tasks to complete. Task 0 has no prerequisites and can be executed first. Task 1 requires task 0 to be completed first. The valid execution order is [0, 1], so all tasks can be completed successfully.

Example 2

Input

numTasks = 2
dependencies = [[1,0],[0,1]]

Output

false

Explanation

There are 2 tasks with a circular dependency. Task 1 requires task 0, and task 0 requires task 1. Neither task can start because each is waiting for the other, creating a deadlock. It is impossible to complete all tasks.

Example 3

Input

numTasks = 4
dependencies = [[1,0],[2,0],[3,1],[3,2]]

Output

true

Explanation

With 4 tasks and 4 dependencies: task 0 has no prerequisites, tasks 1 and 2 both require task 0, and task 3 requires both tasks 1 and 2. A valid execution order is [0, 1, 2, 3] or [0, 2, 1, 3]. No cycles exist, so all tasks can be completed.

Constraints

1 ≤ numTasks ≤ 2000
0 ≤ dependencies.length ≤ 5000
dependencies[i].length == 2
0 ≤ taskᵢ, requiredTaskᵢ < numTasks
All dependency pairs dependencies[i] are unique

Preparing your editor. You can read the problem while it loads.

Task Dependency Validator

Medium

You are given a project management system that needs to schedule numTasks tasks, labeled from 0 to numTasks - 1 . Some tasks have prerequisite requirements that must be satisfied before they can begin execution. You are provided with an array dependencies where each element dependencies[i] = [taskᵢ, requiredTaskᵢ] indicates that requiredTaskᵢ must be completed before taskᵢ can start. In other words, there is a directed dependency from requiredTaskᵢ to taskᵢ . For example, the dependency [3, 1] means that task 1 must be finished before task 3 can begin. Your goal is to determine whether it is possible to complete all tasks given these dependency constraints. If the dependencies form a valid execution order (no circular dependencies exist), return true . Otherwise, if there exists a cycle in the dependencies that makes it impossible to complete all tasks, return false . This is fundamentally a cycle detection problem in a directed graph, where tasks are nodes and dependencies are directed edges. The problem can be solved using: Depth-First Search (DFS) with three-color marking to detect back edges Breadth-First Search (BFS) using Kahn's algorithm for topological sorting Topological Sort verification - if a valid topological order exists, there are no cycles The key insight is that a valid task ordering exists if and only if the dependency graph is a Directed Acyclic Graph (DAG) . Any cycle in the graph means there's a mutual dependency that cannot be resolved, making it impossible to complete all tasks.

Example 1

Input

numTasks = 2
dependencies = [[1,0]]

Output

true

Explanation

Example 2

Input

numTasks = 2
dependencies = [[1,0],[0,1]]

Output

false

Explanation

Example 3

Input

numTasks = 4
dependencies = [[1,0],[2,0],[3,1],[3,2]]

Output

true

Explanation

Constraints

1 ≤ numTasks ≤ 2000
0 ≤ dependencies.length ≤ 5000
dependencies[i].length == 2
0 ≤ taskᵢ, requiredTaskᵢ < numTasks
All dependency pairs dependencies[i] are unique