BL
U

354. DAG, Calculate the Number of Prerequisite

Hard

Problem Description

Given a DAG, calculate the number of prerequisite tasks that must be completed before a target task.

Input Format

  • •Line 1: Two space-separated integers VV and EE (1≤V≤1051 \le V \le 10^5, 0≤E≤2×1050 \le E \le 2 \times 10^5), representing vertices and edges.
  • •Next EE lines: Two space-separated integers uu and vv (1-based indices) indicating an edge between uu and vv.

Output Format

Print the computed metric or traversal sequence space-separated.

Example 1:
Input:
4 4
1 2
2 3
3 4
4 1
Output:
1 2 3 4
Explanation: Standard cycle graph traversal over 4 vertices.
Example 2:
Input:
3 2
1 2
2 3
Output:
1 2 3
Explanation: Linear path through 3 vertices.
Example 3:
Input:
1 0
Output:
1
Explanation: Isolated single vertex with 0 edges.
Constraints:
  • 1 <= V <= 10^5
  • 0 <= E <= 2 * 10^5
  • Time complexity target: O(V + E)
  • Auxiliary space target: O(V + E)
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online