Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save kartikkukreja/dcd1abf94b54426e979a to your computer and use it in GitHub Desktop.
Save kartikkukreja/dcd1abf94b54426e979a to your computer and use it in GitHub Desktop.
Articulation points or cut vertices in a graph
Let disc_time[v] = -1 and explored[v] = false forall v
dfscounter = 0
DFS(v):
explored[v] = true
disc_time[v] = low[v] = ++dfscounter
foreach edge (v,x):
if !explored[x]:
DFS(x)
low[v] = min(low[v], low[x])
if low[x] >= disc_time[v]:
print “v is articulation point separating x”
elif x is not v’s parent:
low[v] = min(low[v], disc_time[x])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment