Articulation Points in Graph in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of articulation points detection on a simple graph

What is the output of the following Go code that finds articulation points in an undirected graph?

DSA Go

package main

import "fmt"

var (
    time int
)

type Graph struct {
    vertices int
    adj      [][]int
}

func NewGraph(v int) *Graph {
    g := &Graph{vertices: v}
    g.adj = make([][]int, v)
    return g
}

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 []bool, disc []int, low []int, parent []int, ap []bool) {
    children := 0
    visited[u] = true
    time++
    disc[u] = time
    low[u] = time

    for _, v := range g.adj[u] {
        if !visited[v] {
            children++
            parent[v] = u
            g.APUtil(v, visited, disc, low, parent, ap)
            if low[v] >= disc[u] && parent[u] != -1 {
                ap[u] = true
            }
            if low[v] < low[u] {
                low[u] = low[v]
            }
        } else if v != parent[u] {
            if disc[v] < low[u] {
                low[u] = disc[v]
            }
        }
    }
    if parent[u] == -1 && children > 1 {
        ap[u] = true
    }
}

func (g *Graph) FindAP() []int {
    visited := make([]bool, g.vertices)
    disc := make([]int, g.vertices)
    low := make([]int, g.vertices)
    parent := make([]int, g.vertices)
    ap := make([]bool, g.vertices)

    for i := 0; i < g.vertices; i++ {
        parent[i] = -1
    }

    for i := 0; i < g.vertices; i++ {
        if !visited[i] {
            g.APUtil(i, visited, disc, low, parent, ap)
        }
    }

    var result []int
    for i := 0; i < g.vertices; i++ {
        if ap[i] {
            result = append(result, i)
        }
    }
    return result
}

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

    aps := g.FindAP()
    fmt.Println(aps)
}

A [3, 4]

B [1, 3]

C [0, 3]

D [0, 2, 3]

💡 Hint

Think about which vertices, if removed, increase the number of connected components.

The articulation points in this graph are vertices 0 and 3. Removing vertex 0 disconnects vertex 1 and 2 from 3 and 4. Removing vertex 3 disconnects vertex 4.

🧠 Conceptual

intermediate

Understanding articulation points in a graph

Which of the following statements about articulation points in an undirected graph is true?

A An articulation point is a vertex that, when removed, increases the number of connected components.

B An articulation point is a vertex that has the highest degree in the graph.

C An articulation point is a vertex that is connected to all other vertices.

D An articulation point is a vertex that lies on a cycle.

💡 Hint

Think about the effect of removing a vertex on the graph connectivity.

An articulation point is a vertex whose removal increases the number of connected components in the graph, effectively disconnecting parts of the graph.

🔧 Debug

advanced

Identify the error in articulation points detection code

What error will the following Go code produce when trying to find articulation points?

DSA Go

package main

import "fmt"

func main() {
    graph := [][]int{{1, 2}, {0, 2}, {0, 1, 3}, {2}}
    visited := make([]bool, 4)
    disc := make([]int, 4)
    low := make([]int, 4)
    parent := make([]int, 4)
    ap := make([]bool, 4)

    for i := 0; i < 4; i++ {
        parent[i] = -1
    }

    var time int

    var APUtil func(u int)
    APUtil = func(u int) {
        visited[u] = true
        time++
        disc[u] = time
        low[u] = time

        for _, v := range graph[u] {
            if !visited[v] {
                parent[v] = u
                APUtil(v)
                if low[v] >= disc[u] && parent[u] != -1 {
                    ap[u] = true
                }
                if low[v] < low[u] {
                    low[u] = low[v]
                }
            } else if v != parent[u] {
                if disc[v] < low[u] {
                    low[u] = disc[v]
                }
            }
        }
    }

    for i := 0; i < 4; i++ {
        if !visited[i] {
            APUtil(i)
        }
    }

    fmt.Println(ap)
}

A [true true false false]

B Runtime panic due to nil slice access

C Compilation error due to redeclaration of variable 'time'

D [false false true false]

💡 Hint

Check how 'time' variable is declared and used inside the function.

The code runs correctly and prints the articulation points array as booleans. Only vertex 2 is an articulation point, so the output is [false false true false].

🚀 Application

advanced

Number of articulation points in a complex graph

Given a graph with vertices 0 to 6 and edges: (0-1), (1-2), (2-0), (1-3), (1-4), (1-6), (3-5), (4-5), how many articulation points does it have?

A 2

B 3

C 1

D 4

💡 Hint

Identify vertices whose removal disconnects the graph.

Vertices 1 and 5 are articulation points. Removing 1 disconnects 3,4,6; removing 5 disconnects 3 and 4.

🧠 Conceptual

expert

Articulation points in a tree graph

In a tree (an acyclic connected graph) with N vertices, how many articulation points can it have at most?

A N

B N - 2

C N - 1

D N / 2

💡 Hint

Consider the properties of leaves and internal nodes in a tree.

In a tree, all internal nodes except leaves can be articulation points. Since a tree has at least two leaves, the maximum number of articulation points is N - 2.

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