Graph Theory37 sections · 1633 units
Open in Course

Articulation Points - Trace

(Step-by-step execution)

Trace on input n=5n=5, edges [[0,1],[1,2],[2,0],[1,3],[3,4]][[0,1],[1,2],[2,0],[1,3],[3,4]]: DFS from 00: disc[0]=0. Visit 11: disc[1]=1. Visit 22: disc[2]=2. Back edge 202-0: low[2]=0. Backtrack: low[1]=0. Visit 33: disc[3]=3.

Visit 44: disc[4]=4. Backtrack: low[3]=3 >= disc[1]=1, add 11. Backtrack: low[4]=4 >= disc[3]=3, add 33. Articulation points: [1,3][1, 3]. Both vertices satisfy the condition.