# Tarjan's Algorithm and Finding Articulation Points / Cut Vertices

Get started**🕉**

# জয় শ্রী রাম

Let G = (V, E) be a connected, undirected graph. An

**articulation point**of G is a vertex whose removal disconnects G. A

**bridge**of G is an edge whose removal disconnects G. A

**biconnected component**of G is a maximal set of edges such that any two edges in the set lie on a common simple cycle. A

**simple cycle**is a cycle with no repeated vertex.

The concept of

**Articulation Point**is explained in the video below. Please excuse my speech impediment while watching the video. Thank you for your patience.

**IMPORTANT ANNOUNCEMENT: For the most accurate code please see the code below, rather than looking at the code discussed in the video, as I have later found a bug in the code discussed in the video. Basically the constraints discussed for "parents" apply to all ancestors as well. The corrected version is posted in this chapter, please see the code below the video.**

#### Pseudocode:

```
GetArticulationPoints(i, d)
visited[i] := true
depth[i] := d
low[i] := d
childCount := 0
isArticulation := false
for each ni in adj[i] do
if not visited[ni] then
parent[ni] := i
GetArticulationPoints(ni, d + 1)
childCount := childCount + 1
if low[ni] ≥ depth[i] then
isArticulation := true
low[i] := Min (low[i], low[ni])
else if ni ≠ parent[i] then
low[i] := Min (low[i], depth[ni])
if (parent[i] ≠ null and isArticulation) or (parent[i] = null and childCount > 1) then
Output i as articulation point
```

#### Working Solution:

**Java code:**

Login to Access Content

**Python code:**

Login to Access Content