Articulation Points in Graph in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the discovery time for each node.

DSA Python

disc = [-1] * [1]

Drag options to blanks, or click blank then click option'

Alen(graph)

Bgraph

Cn

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 or n without defining n.

Using graph directly instead of its length.

We use the length of the graph (number of nodes) to create the discovery time list initialized with -1.

2fill in blank

medium

Complete the code to update the low time of the current node after visiting a neighbor.

DSA Python

low[u] = min(low[u], [1][v])

Drag options to blanks, or click blank then click option'

Adisc

Bparent

Clow

Dvisited

Attempts:

3 left

💡 Hint

Common Mistakes

Using disc[v] instead of low[v].

Using parent[v] which is not a time value.

We update low[u] with the minimum of its current low[u] and low[v] of the neighbor.

3fill in blank

hard

Fix the error in the condition to check if a node is an articulation point for a non-root node.

DSA Python

if parent[u] != -1 and low[v] >= [1][u]:
    ap[u] = True

Drag options to blanks, or click blank then click option'

Alow

Bdisc

Cparent

Dvisited

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing low[v] with low[u] instead of disc[u].

Using parent[u] which is not a time value.

We compare low[v] with disc[u] to check if u is an articulation point.

4fill in blank

hard

Fill both blanks to correctly check if the root node is an articulation point.

DSA Python

if parent[u] == -1 and [1] > 1:
    ap[u] = [2]

Drag options to blanks, or click blank then click option'

Achildren

Bap[u]

CTrue

DFalse

Attempts:

3 left

💡 Hint

Common Mistakes

Setting ap[u] to False instead of True.

Checking children <= 1 instead of > 1.

The root node is an articulation point if it has more than one child, so we check children > 1 and set ap[u] to True.

5fill in blank

hard

Fill all three blanks to correctly implement the DFS function header and recursive call.

DSA Python

def dfs(u, [1], [2], [3]):
    # function body
    for v in graph[u]:
        if disc[v] == -1:
            dfs(v, parent, disc, low)

Drag options to blanks, or click blank then click option'

Aparent

Bdisc

Clow

Dvisited

Attempts:

3 left

💡 Hint

Common Mistakes

Missing parent parameter.

Passing visited instead of low.

The dfs function takes parameters u, parent, disc, and low. The recursive call passes parent, disc, and low.

Practice

1. What is an articulation point in a graph?

easy

A. A vertex connected to all other vertices

B. A vertex with the highest degree in the graph

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

D. A vertex that forms a cycle with its neighbors

Solution

1. Step 1: Understand the definition of articulation point

   An articulation point is a vertex in a graph whose removal disconnects the graph or increases the number of connected components.

2. Step 2: Compare options with definition

   A vertex that, when removed, increases the number of connected components matches this definition exactly. Other options describe different concepts.

3. Final Answer:

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

4. Quick Check:

   Articulation point = vertex disconnecting graph [OK]

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

Common Mistakes:

• Confusing articulation point with highest degree vertex
• Thinking articulation point forms cycles
• Assuming articulation point connects to all vertices

2. Which of the following is the correct way to initialize the discovery time array for articulation point detection in Python?

easy

A. discovery = list(range(n))

B. discovery = [-1] * n

C. discovery = [0] * n

D. discovery = None

Solution

1. Step 1: Understand initialization purpose

   The discovery time array stores the time when each vertex is first visited. Initializing with -1 means unvisited.

2. Step 2: Check options

   discovery = [-1] * n initializes all values to -1, indicating unvisited vertices. discovery = [0] * n sets all to 0, which can be confused with a valid time. discovery = list(range(n)) assigns increasing numbers, which is incorrect. discovery = None sets None, which is invalid for indexing.

3. Final Answer:

   discovery = [-1] * n -> Option B

4. Quick Check:

   Unvisited vertices marked as -1 [OK]

Hint: Use -1 to mark unvisited nodes in discovery array [OK]

Common Mistakes:

• Initializing discovery with zeros causing confusion
• Using range which sets wrong discovery times
• Setting discovery to None causing errors

3. What will be the output articulation points for the following graph represented as adjacency list?

graph = {0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2, 4, 5], 4: [3, 5], 5: [3, 4]}

medium

A. [2, 3]

B. [0, 3]

C. [1, 4]

D. [3]

Solution

1. Step 1: Analyze graph structure

   Vertices 0,1,2 form a triangle (cycle). Vertex 3 connects this triangle to vertices 4 and 5, which form another cycle.

2. Step 2: Identify articulation points

   Removing vertex 2 disconnects vertex 3 and its connected cycle from the triangle. Removing vertex 3 disconnects vertices 4 and 5 from the rest. So articulation points are 2 and 3.

3. Final Answer:

   [2, 3] -> Option A

4. Quick Check:

   Vertices breaking connectivity = 2, 3 [OK]

Hint: Check vertices connecting two or more components [OK]

Common Mistakes:

• Ignoring articulation point at vertex 2
• Missing vertex 3 as articulation point
• Confusing cycle vertices as articulation points

4. Identify the bug in this articulation point detection code snippet:

def dfs(u, parent):
    visited[u] = True
    discovery[u] = time
    low[u] = time
    time += 1
    children = 0
    for v in graph[u]:
        if not visited[v]:
            children += 1
            dfs(v, u)
            low[u] = min(low[u], low[v])
            if parent != -1 and low[v] >= discovery[u]:
                articulation[u] = True
        elif v != parent:
            low[u] = min(low[u], discovery[v])
    if parent == -1 and children > 1:
        articulation[u] = True

medium

A. Variable 'time' is not declared global or passed, causing incorrect increments

B. The condition 'low[v] >= discovery[u]' should be '>' instead of '>='

C. The 'children' count is not incremented correctly

D. The check 'elif v != parent' should be 'if v == parent'

Solution

1. Step 1: Check variable usage in recursion

   The variable 'time' is incremented inside dfs but not declared global or passed as argument, so increments won't persist across calls.

2. Step 2: Verify other conditions

   Conditions and increments for 'children' and articulation logic are correct. The 'elif' condition is also correct to update low values.

3. Final Answer:

   Variable 'time' is not declared global or passed, causing incorrect increments -> Option A

4. Quick Check:

   Global time needed for correct discovery times [OK]

Hint: Declare 'time' global or pass it to update correctly [OK]

Common Mistakes:

• Not declaring 'time' global causing discovery errors
• Changing condition '>=' to '>' incorrectly
• Miscounting children in DFS
• Incorrectly checking parent in else condition

5. Given a connected undirected graph with 7 vertices and edges:

edges = [(0,1),(1,2),(2,0),(1,3),(3,4),(4,5),(5,3),(5,6)]

Which vertices are articulation points?

hard

A. [0, 3, 6]

B. [2, 4, 5]

C. [1, 4, 6]

D. [1, 3, 5]

Solution

1. Step 1: Analyze graph structure

   Vertices 0,1,2 form a triangle (cycle). Vertex 1 connects to vertex 3, which connects to a cycle 3-4-5 and vertex 5 connects to 6.

2. Step 2: Identify articulation points

   Removing vertex 1 disconnects 3 and beyond from 0 and 2. Removing vertex 3 disconnects 4 and 5 from 1. Removing vertex 5 disconnects 6 from the rest. So articulation points are 1, 3, and 5.

3. Final Answer:

   [1, 3, 5] -> Option D

4. Quick Check:

   Vertices disconnecting parts = 1, 3, 5 [OK]

Hint: Find vertices connecting cycles or leaf nodes [OK]

Common Mistakes:

• Missing vertex 1 as articulation point
• Including leaf vertex 6 incorrectly
• Ignoring vertex 5's role in connectivity