Topological Sort

PayPal's "Topological Sort" interview question typically involves performing a topological sort on a directed acyclic graph (DAG), often using either DFS (post-order traversal) or BFS (Kahn's algorithm with indegrees), to linearize nodes such that for every directed edge from u to v, u comes before v.[1][2]

Problem Statement

Given a directed graph (usually as an adjacency list), return a topological ordering of the nodes if the graph is a DAG; otherwise, indicate if a cycle exists (e.g., return empty list or flag). The graph may have nodes labeled 0 to n-1 or custom identifiers. Both DFS (recursive post-order) and BFS (queue-based indegree reduction) implementations are expected, with BFS preferred for handling same-level nodes naturally.[2][3][1]

Input Format

• n: Number of nodes (1 ≤ n ≤ 10^4).
• edges: List of directed edges, e.g., [[u1,v1], [u2,v2], ...] where 0 ≤ ui, vi < n (up to 10^5 edges).
• Graph may include isolated nodes or disconnected components.[4][5]

Output Examples

Example 1: Valid DAG.
Input: n=4, edges=[,,,][3][1][2] Graph: 0→1←2, 1→3
Output: (or, – valid orders)[1][2][3][4]

Example 2: Cycle detected.
Input: n=2, edges=[,][1] Output: [] (cycle exists, no valid sort)[2]

Example 3: Disconnected graph.
Input: n=3, edges=[][1] Output: (or – isolated 2 can go anywhere)[3][2][1]

Constraints

• 1 ≤ n ≤ 10^4 nodes.
• 0 ≤ |edges| ≤ 10^5.
• Graph is directed; may contain cycles (must detect).
• No self-loops assumed.
• Time: O(V + E), Space: O(V + E).[5][4]