Topological Sort Feasibility

Given a directed graph, determine whether a topological ordering exists. Pattern focus: Cycle Detection. A topological ordering exists if and only if the graph is a DAG.

Input Format

n = number of vertices, edges = directed edge list

Output Format

true if a topological ordering exists

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9

Examples

Example 1:

Input:

n = 4
edges = [[0,1],[1,2],[2,3]]

Output:

true

Explanation:

The graph is a DAG, so a topological ordering exists.

Example 2:

Input:

n = 4
edges = [[0,1],[1,2],[2,0]]

Output:

false

Explanation:

A directed cycle prevents any topological order.

Example 3:

Input:

n = 2
edges = [[0,1]]

Output:

true
Loading...
Topological Sort Feasibility - Topological Sort