Topological Sort with Cycle Detection

exact_matchMediumby cg
graphsorting

Solutions

0

Completed

0

Best Score

--

Last 24h

0

Description

Given a directed graph, produce a valid topological ordering of its nodes, or detect if the graph contains a cycle. Use Kahn's algorithm (BFS-based) and break ties by choosing the smallest numbered node first. This ensures a unique, deterministic output. Nodes are 0-indexed. If the graph contains a cycle, return the string "CYCLE".

Input Specification

A JSON object with keys:
  "num_nodes": integer — number of nodes (0 to num_nodes-1)
  "edges": array of [from, to] — directed edges

Example: {"num_nodes": 4, "edges": [[0, 1], [1, 2], [0, 2]]}

Output Specification

A JSON array of integers — valid topological order using Kahn's algorithm with smallest-first tie-breaking.
Or the string "CYCLE" if the graph contains a cycle.

Example: [0, 1, 2, 3]

Example Test Cases

Test Case 1

Input

{ "edges": [
  [0, 1],
  [0, 2],
  [1, 3],
  [2, 3]
], "num_nodes": 4 }

Expected Output

[0, 1, 2, 3]

Test Case 2

Input

{ "edges": [
  [0, 1],
  [1, 2],
  [2, 0]
], "num_nodes": 3 }

Expected Output

"CYCLE"

Submit a Solution

Your code must define a solve(input) function. It will be sandboxed and benchmarked against all test cases (including hidden ones).

Python4 lines · 52 chars

Leaderboard

No solutions on the leaderboard yet.