Why Articulation Points in Graph in DSA Python?

The Big Idea

What if one small neighborhood can break your whole city's connection?

The Scenario

Imagine you have a city map with roads connecting different neighborhoods. You want to find which neighborhoods are so important that if they close, parts of the city become unreachable.

The Problem

Trying to check every neighborhood manually to see if closing it breaks the city apart is slow and confusing. You might miss some important spots or spend hours testing each one.

The Solution

Articulation points help you quickly find these critical neighborhoods using a smart method that explores the city map once and spots all key points that connect different areas.

Before vs After

✗ Before

for each neighborhood:
    close it temporarily
    check if city is still connected
    reopen it

✓ After

run DFS once
track discovery and low times
identify articulation points efficiently

What It Enables

This lets you protect or improve the city by focusing on the most crucial neighborhoods that keep everything connected.

Real Life Example

Network engineers use articulation points to find routers or servers that, if they fail, would split the network and cause outages.

Key Takeaways

Manual checking is slow and error-prone.

Articulation points find critical nodes in one smart pass.

Useful for network reliability and city planning.

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