Topological Sort
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.graphs;
/*
* ============================================================================================
* PROBLEM: Topological Sort
* ============================================================================================
*
* ---------------------
* 1. Problem Description
* ---------------------
* Given a Directed Acyclic Graph (DAG) with A nodes and M edges.
* Find a linear ordering of vertices such that for every directed edge u -> v,
* u comes before v.
* * Special Constraints:
* - If multiple valid orderings exist, return the lexicographically smallest one.
* - If the graph is not a DAG (contains a cycle), return an empty array.
*
* ---------------------
* 2. Logical Breakdown & Mathematical Formulation
* ---------------------
* We use Kahn's Algorithm (Indegree-based BFS) to generate the sort.
*
* Step 1: In-degree Calculation
* Create an array indegree of size A+1. For every edge u -> v, increment indegree[v].
*
* Step 2: Lexicographical Handling
* Standard Kahn's uses a Queue. To get the lexicographically smallest result,
* we use a Min-Priority Queue (Min-Heap). This ensures that among all nodes
* currently having an in-degree of 0, we always pick the one with the smallest label.
*
* Step 3: Process Nodes
* 1. Add all nodes with indegree == 0 to the Priority Queue.
* 2. While the Priority Queue is not empty:
* a. Extract the smallest node u.
* b. Add u to the result list.
* c. For each neighbor v of u:
* - Decrement indegree[v].
* - If indegree[v] reaches 0, add v to the Priority Queue.
*
* Step 4: Cycle Detection
* If the number of nodes in the result list is less than A, the graph has a cycle.
* Return an empty array.
*
* ---------------------
* 3. Constraints & Complexity Analysis
* ---------------------
* Constraints:
* 1 <= A <= 10^5
* 1 <= M <= 10^5
*
* Time Complexity:
* O(A log A + M log A)
* - Building graph: O(M)
* - Each node added/removed from Min-Heap: O(A log A)
* - Each edge processed: O(M log A)
*
* Space Complexity:
* O(A + M) - Adjacency list and in-degree array.
*
* ============================================================================================
/
public class TopologicalSort {
public int[] solve(int A, int[][] edges4) {
// TODO: Implement solution
return new int[0];
}
}