15-special-dfs

Unit 15: Specialized DFS

This unit covers some extensions to DFS and the problems they solve:

• Opened/closed node states
• Edge types (tree, back, cross)
• Cycle check
• Node timestamps and visibility (dfs_num and dfs_low)
• Bridges
• Articulation points

Tarjan's SCC algorithm was left out for the time being because it is more complex and difficult to remember than Kosaraju's.

Prerequisites

• Unit 6: Graph basics
• Unit 14: Graph traversal

Practice problems

Basic

• UVa 315 - Network (articulation points)
• UVa 796 - Critical Links (bridges, assume N <= 10000, input tricky, don't hesitate to ask for help!)

Variants

• UVa 610 - Street Directions (very interesting!)
• UVa 10765 - Doves and Bombs