Topological sort

Question 1

What is Topological Sort and when is it used?

Answer 1

Orders nodes in DAG such that dependencies are respected.
Use Case: Course scheduling, task dependencies.

Example: [Course Schedule II]. Action: Verbalize use case aloud.

Question 2

What are the key steps in Topological Sort?

Answer 2

1. Build adjacency list and in-degree count.
2. Queue nodes with in-degree 0.
3. Process nodes, reduce in-degrees, add new zeros.

Action: Explain steps for [Course Schedule II] aloud.

Question 3

How does Topological Sort apply to [Course Schedule II]?

Answer 3

Find valid course order. Use queue to process courses with no prerequisites, update dependencies.

Action: Verbalize solution logic aloud.

Question 4

What are the complexity and gotchas of Topological Sort?

Answer 4

Time: O(V+E), Space: O(V+E).
Gotchas: Cycles, disconnected graph.

Action: List edge cases for [Course Schedule II] aloud.

Question 5

Code example for Topological Sort.

Answer 5

```python
from typing import List
from collections import defaultdict, deque
def find_order(num_courses: int, prerequisites: List[List[int]]) -> List[int]:
graph = defaultdict(list)
in_degree = [0] * num_courses
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1
queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return result if len(result) == num_courses else []
~~~