DAA HT23, Strongly connected components

Created: May 23, 2023 | About these notes | View in context | Study these flashcards

---

• [[Course - Design and Analysis of Algorithms HT23]]^U

Flashcards

What a strongly connected component of a graph $G$?

---

A maximal set of vertices $C \subseteq V$ such that for every pair of vertices $u \leadsto v$ and $v \leadsto u$.

When constructing a topological sort of a DAG, what order do you consider vertices in?

---

Reverse finishing time.

Proofs

---

Related posts

• [[Course - Design and Analysis of Algorithms HT23]]^U

  (outgoing)
• [[Notes - Logic and Proof MT24, 2-CNF formulas]]^U

  (incoming)
• [[Notes - DAA HT23, Graphs]]^U

  (incoming)
• [[List of algorithms to memorise for DAA]]^U

  (incoming)
• [[Notes - DAA HT23, Depth-first search]]^U

  (sim: 0.596)
• [[Lecture - DAA HT23, XIII]]^U

  (sim: 0.545)
• [[Lecture - DAA HT23, XIV]]^U

  (sim: 0.545)