← Quiz: Topological Sort: all 15 questions
Quiz: Topological Sort · Question 10 of 15
Why is the longest path easy to find in a DAG but hard in a general graph?
Why is the longest path easy to find in a DAG but hard in a general graph?
- A.DAGs have no weights
- B.DAGs have only one path between any two nodes
- C.Longest path is always easy
- D.In topological order, every node's predecessors are processed first, so a simple DP over the order works
Answer & explanation
Correct answer: In topological order, every node's predecessors are processed first, so a simple DP over the order works
Processing in topological order means dist[v] = max over incoming edges is final when v is reached. Cycles break this.
Can you get the rest right without peeking?
Take the timed Quiz: Topological Sort quiz free. Pass it to earn XP and count towards your certificate.
Start the quiz →