Articulation Point
Definition
Articulation point or cut vertex is some node in a Graph such that, if that node (and all edges associated with it) are deleted, the number of components in the initial graph increases (If the graph was connected before now it will form multiple disconnected components).
Intuition behind the algorithm
Todo
Problems
- LightOJ 1063 - Ant Hills (
Straightforward Articulation Point)
Bridge
Definition
Cut edge or Bridge is some edge in a Graph such that, if that edge is deleted the number of components in the initial graph increases (If the graph was connected before now it will form multiple disconnected components).
Intuition behind the algorithm
Todo
Problems
- LightOJ 1026 - Critical Links (
Straightforward Bridge, need to print the bridges in sorted manner [Use set/map])
We can only see a short distance ahead, but we can see plenty there that needs to be done.