Topological Sort (Kahn's Algorithm) - Classic Problems | Repovive

CLS17. Topological Sort (Kahn's Algorithm)

1s256 MB

Given a directed acyclic graph (DAG) with $n$ vertices and $m$ edges, find a topological ordering of the vertices using Kahn's algorithm (BFS-based).

A topological ordering is a linear ordering of vertices such that for every directed edge $u \to v$ , vertex $u$ comes before $v$ .

If multiple valid orderings exist, output the lexicographically smallest one.

If the graph contains a cycle, output -1.

\begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array}

\begin{cases} p_1 \quad p_2 \quad \cdots \quad p_n & \text{lexicographically smallest topological order} \\ -1 & \text{if a cycle exists} \end{cases}

Input

Explanation

For this input, the required output is 1 2 3 4.

Output

1 2 3 4

Input

Explanation

For this input, the required output is -1.

Output

-1

Input

Explanation

For this input, the required output is 4 5 1 2 3.

Output

4 5 1 2 3

1s256 MB

Given a directed acyclic graph (DAG) with $n$ vertices and $m$ edges, find a topological ordering of the vertices using Kahn's algorithm (BFS-based).

A topological ordering is a linear ordering of vertices such that for every directed edge $u \to v$ , vertex $u$ comes before $v$ .

If multiple valid orderings exist, output the lexicographically smallest one.

If the graph contains a cycle, output -1.

\begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array}

\begin{cases} p_1 \quad p_2 \quad \cdots \quad p_n & \text{lexicographically smallest topological order} \\ -1 & \text{if a cycle exists} \end{cases}

Input

Explanation

For this input, the required output is 1 2 3 4.

Output

1 2 3 4

Input

Explanation

For this input, the required output is -1.

Output

-1

Input

Explanation

For this input, the required output is 4 5 1 2 3.

Output

4 5 1 2 3