Articulation Points in Graph in DSA Go

Mental Model

An articulation point is a node in a graph that, if removed, breaks the graph into more pieces. It shows where the graph is fragile.

Analogy: Imagine a city connected by roads. Some intersections are so important that if they close, parts of the city become unreachable. These intersections are articulation points.

Graph example:
  1
 / \
2 - 3 - 4
     |
     5

Here, node 3 is an articulation point because removing it splits the graph.

Dry Run Walkthrough

Input: Graph with edges: 1-2, 1-3, 2-3, 3-4, 3-5

Goal: Find all articulation points in the graph

Step 1: Start DFS from node 1, set discovery time and low value

Visited: 1 (disc=1, low=1)
Stack: [1]

Why: We begin exploring from node 1 to find articulation points

Step 2: Visit node 2 from 1, set discovery and low values

Visited: 1 (disc=1, low=1), 2 (disc=2, low=2)
Stack: [1,2]

Why: Explore neighbors to find back edges and update low values

Step 3: Visit node 3 from 2, set discovery and low values

Visited: 1 (disc=1, low=1), 2 (disc=2, low=2), 3 (disc=3, low=3)
Stack: [1,2,3]

Why: Continue DFS to deeper nodes

Step 4: From 3, visit node 4, set discovery and low values

Visited: 1 (disc=1, low=1), 2 (disc=2, low=2), 3 (disc=3, low=3), 4 (disc=4, low=4)
Stack: [1,2,3,4]

Why: Explore child nodes to check connectivity

Step 5: Node 4 has no unvisited neighbors, backtrack and update low of 3 to min(low3, low4)=3

Visited: ... low[3]=3
Stack: [1,2,3]

Why: Update low values to reflect earliest reachable ancestor

Step 6: From 3, visit node 5, set discovery and low values

Visited: ... 5 (disc=5, low=5)
Stack: [1,2,3,5]

Why: Explore all children of 3

Step 7: Node 5 has no unvisited neighbors, backtrack and update low of 3 to min(low3, low5)=3

Visited: ... low[3]=3
Stack: [1,2,3]

Why: Update low values after exploring all children

Step 8: Backtrack to 2, update low of 2 to min(low2, low3)=2; check articulation condition for 3

Visited: ... low[2]=2
Stack: [1,2]

Why: Check if 3 is articulation point: low[child]>=disc[parent]

Step 9: Backtrack to 1, update low of 1 to min(low1, low2)=1; check articulation condition for 1

Visited: ... low[1]=1
Stack: [1]

Why: Root node with more than one child is articulation point

Result:

Articulation points: 3
Graph after DFS:
1 (disc=1, low=1)
2 (disc=2, low=2)
3 (disc=3, low=3) ← articulation point
4 (disc=4, low=4)
5 (disc=5, low=5)

Annotated Code

DSA Go

package main

import (
	"fmt"
)

type Graph struct {
	adj map[int][]int
	time int
}

func NewGraph() *Graph {
	return &Graph{adj: make(map[int][]int)}
}

func (g *Graph) AddEdge(u, v int) {
	g.adj[u] = append(g.adj[u], v)
	g.adj[v] = append(g.adj[v], u)
}

func (g *Graph) APUtil(u int, visited map[int]bool, disc map[int]int, low map[int]int, parent map[int]int, ap map[int]bool) {
	visited[u] = true
	g.time++
	disc[u] = g.time
	low[u] = g.time
	children := 0

	for _, v := range g.adj[u] {
		if !visited[v] {
			children++
			parent[v] = u
			// advance DFS to child v
			g.APUtil(v, visited, disc, low, parent, ap)

			// update low[u] based on child's low
			if low[v] < low[u] {
				low[u] = low[v]
			}

			// articulation point check for non-root
			if parent[u] != -1 && low[v] >= disc[u] {
				ap[u] = true
			}
		} else if v != parent[u] {
			// update low[u] for back edge
			if disc[v] < low[u] {
				low[u] = disc[v]
			}
		}
	}

	// articulation point check for root
	if parent[u] == -1 && children > 1 {
		ap[u] = true
	}
}

func (g *Graph) FindArticulationPoints() []int {
	visited := make(map[int]bool)
	disc := make(map[int]int)
	low := make(map[int]int)
	parent := make(map[int]int)
	ap := make(map[int]bool)

	for u := range g.adj {
		visited[u] = false
		parent[u] = -1
		disc[u] = 0
		low[u] = 0
		ap[u] = false
	}

	for u := range g.adj {
		if !visited[u] {
			g.APUtil(u, visited, disc, low, parent, ap)
		}
	}

	result := []int{}
	for u, isAP := range ap {
		if isAP {
			result = append(result, u)
		}
	}
	return result
}

func main() {
	g := NewGraph()
	g.AddEdge(1, 2)
	g.AddEdge(1, 3)
	g.AddEdge(2, 3)
	g.AddEdge(3, 4)
	g.AddEdge(3, 5)

	aps := g.FindArticulationPoints()
	fmt.Print("Articulation points: ")
	for i, v := range aps {
		if i > 0 {
			fmt.Print(", ")
		}
		fmt.Print(v)
	}
	fmt.Println()
}

visited[u] = true g.time++ disc[u] = g.time low[u] = g.time

Mark node u visited and set discovery and low times

for _, v := range g.adj[u] { if !visited[v] { children++ parent[v] = u g.APUtil(v, visited, disc, low, parent, ap)

DFS to unvisited child v, track children count

if low[v] < low[u] { low[u] = low[v] }

Update low[u] with child's low to find earliest reachable ancestor

if parent[u] != -1 && low[v] >= disc[u] { ap[u] = true }

Mark u as articulation point if child's low is not earlier than u's discovery

else if v != parent[u] { if disc[v] < low[u] { low[u] = disc[v] } }

Update low[u] for back edge to ancestor v

if parent[u] == -1 && children > 1 { ap[u] = true }

Root node with multiple children is articulation point

Output

Articulation points: 3

Complexity Analysis

Time: O(V + E) because we visit each vertex and edge once during DFS

Space: O(V) for storing visited, discovery, low, parent, and articulation arrays

vs Alternative: Naive approach checks connectivity after removing each node, costing O(V*(V+E)), much slower than DFS-based O(V+E)

Edge Cases

Graph with no edges

No articulation points because no connectivity to break

DSA Go

if parent[u] == -1 && children > 1 {
 ap[u] = true
}

Graph with single node

No articulation points because removing the only node leaves empty graph

DSA Go

if parent[u] == -1 && children > 1 {
 ap[u] = true
}

Graph with multiple disconnected components

Algorithm runs DFS on each component separately and finds articulation points in each

DSA Go

for u := range g.adj {
 if !visited[u] {
  g.APUtil(u, visited, disc, low, parent, ap)
 }
}

When to Use This Pattern

When a problem asks for nodes whose removal disconnects the graph, use articulation points detection with DFS and low-link values.

Common Mistakes

Mistake: Not updating low[u] for back edges to ancestors
Fix: Add condition to update low[u] when visiting a visited neighbor that is not parent

Mistake: Marking root node as articulation point without checking children count
Fix: Only mark root as articulation point if it has more than one child in DFS tree

Summary

Finds nodes that disconnect the graph if removed

Use when you need to identify critical points in network connectivity

Track discovery and low times during DFS to detect articulation points

Practice

1. What is an articulation point in a graph?

easy

A. A vertex with the highest degree in the graph

B. A vertex that, when removed, increases the number of connected components

C. A vertex that has no edges connected to it

D. A vertex that forms a cycle with other vertices

Solution

1. Step 1: Understand the definition of articulation point

   An articulation point is a vertex that, if removed, breaks the graph into more pieces (connected components).

2. Step 2: Compare options with definition

   Only A vertex that, when removed, increases the number of connected components matches this definition exactly.

3. Final Answer:

   A vertex that, when removed, increases the number of connected components -> Option B

4. Quick Check:

   Articulation point = vertex increasing components when removed [OK]

Hint: Articulation point breaks graph connectivity when removed [OK]

Common Mistakes:

• Confusing articulation point with highest degree vertex
• Thinking articulation point is a vertex with no edges
• Mixing articulation point with cycle vertices

2. Which Go code snippet correctly declares a graph as an adjacency list for articulation point detection?

easy

A. graph := make(map[int][]int)

B. graph := make(map[int]int)

C. graph := make([]int, n)

D. graph := make([][]int, n)

Solution

1. Step 1: Identify correct data structure for adjacency list

   An adjacency list maps each vertex to a list of connected vertices, so map[int][]int is correct.

2. Step 2: Check other options

   graph := make([][]int, n) is a slice of slices, which can work but usually fixed size; graph := make(map[int]int) is map[int]int (single int), not list; graph := make([]int, n) is slice of ints, not adjacency list.

3. Final Answer:

   graph := make(map[int][]int) -> Option A

4. Quick Check:

   Adjacency list = map vertex to list of neighbors [OK]

Hint: Adjacency list uses map[int][]int in Go [OK]

Common Mistakes:

• Using map[int]int instead of map[int][]int
• Using slice of ints instead of slice of slices or map
• Confusing slice initialization with map initialization

3. What is the output of the following Go code snippet that finds articulation points in a graph with edges: 0-1, 1-2, 1-3?

package main
import "fmt"
func main() {
    n := 4
    graph := make(map[int][]int)
    graph[0] = []int{1}
    graph[1] = []int{0, 2, 3}
    graph[2] = []int{1}
    graph[3] = []int{1}
    articulationPoints := []int{}
    // Assume articulation point detection returns [1]
    articulationPoints = append(articulationPoints, 1)
    fmt.Println(articulationPoints)
}

medium

A. []

B. [0, 1]

C. [1]

D. [2, 3]

Solution

1. Step 1: Analyze the graph structure

   Vertices 0,1,2,3 with edges 0-1, 1-2, 1-3 form a star with center 1.

2. Step 2: Identify articulation points

   Removing vertex 1 disconnects the graph, so 1 is an articulation point; others are not.

3. Final Answer:

   [1] -> Option C

4. Quick Check:

   Center vertex in star graph is articulation point [OK]

Hint: Center vertex connecting others is articulation point [OK]

Common Mistakes:

• Including leaf nodes as articulation points
• Forgetting that removing center disconnects graph
• Assuming multiple articulation points without checking connectivity

4. Find the bug in this Go code snippet for articulation point detection:

func dfs(u, parent int, graph map[int][]int, visited []bool, disc []int, low []int, time *int, ap []bool) {
    visited[u] = true
    disc[u] = *time
    low[u] = *time
    *time = *time + 1
    children := 0
    for _, v := range graph[u] {
        if !visited[v] {
            children++
            dfs(v, u, graph, visited, disc, low, time, ap)
            low[u] = min(low[u], low[v])
            if parent != -1 && low[v] >= disc[u] {
                ap[u] = true
            }
        } else if v != parent {
            low[u] = min(low[u], disc[v])
        }
    }
    if parent == -1 && children > 1 {
        ap[u] = true
    }
}

What is the error?

medium

A. Wrong comparison operator in if condition

B. Missing initialization of visited array

C. Incorrect base case for DFS

D. Incorrect increment syntax for time pointer (*time++)

Solution

1. Step 1: Check pointer increment syntax

   The line '*time++' is invalid in Go; pointer dereference and increment must be done as '*time = *time + 1'.

2. Step 2: Verify other parts

   Visited array initialization, if conditions, and DFS base case are correct.

3. Final Answer:

   Incorrect increment syntax for time pointer (*time++) -> Option D

4. Quick Check:

   Pointer increment in Go uses '*time = *time + 1' [OK]

Hint: Use '*time = *time + 1' to increment pointer value in Go [OK]

Common Mistakes:

• Using '*time++' which is invalid in Go
• Not initializing visited slice before DFS
• Confusing parent check condition
• Missing DFS base case for recursion

5. Given a connected graph with vertices 0 to 5 and edges: 0-1, 1-2, 2-0, 1-3, 3-4, 4-5, 5-3, which vertices are articulation points?

hard

A. [1,3]

B. [1,4]

C. [3]

D. [0,2,4]

Solution

1. Step 1: Analyze the graph structure

   Vertices 0,1,2 form a triangle (cycle), so none are articulation points there. Vertices 3,4,5 form another cycle. Vertex 1 connects these two parts.

2. Step 2: Identify articulation points

   Removing vertex 1 disconnects {0,2} from {3,4,5}. Removing vertex 3 disconnects {0,1,2} from {4,5}. Removing vertex 4 does not disconnect since 5 connects back to 3.

3. Final Answer:

   [1,3] -> Option A

4. Quick Check:

   Vertices connecting cycles or bridges are articulation points [OK]

Hint: Articulation points connect cycles or separate components [OK]

Common Mistakes:

• Including vertices inside cycles as articulation points
• Missing vertex 3 as articulation point
• Assuming all cycle vertices are articulation points