🎙 Free live masterclass · Sun, 29 Nov, 7:00 pm IST · Java Full Stack roadmap Register free →
Skills101
← 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?

  1. A.DAGs have no weights
  2. B.DAGs have only one path between any two nodes
  3. C.Longest path is always easy
  4. 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 →