Topological Sort and DP on DAGs

Define a Directed Acyclic Graph (DAG) and a topological ordering of its vertices.

Prove that a directed graph has a topological ordering if and only if it is a DAG.

Implement topological sort using Kahn's algorithm (a BFS-based approach with in-degree tracking).

Implement topological sort using a DFS-based approach.

Apply DP on a topologically sorted DAG to count the number of distinct paths between two vertices.

Compute the shortest paths from a source vertex in a weighted DAG using DP on the topological order.

Compute the longest paths from a source vertex in a weighted DAG by negating edge weights and finding shortest paths.