Challenge - 5 Problems
Articulation Points Master
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate2:00remaining
Output of articulation points detection on a simple graph
What is the output of the following code that finds articulation points in the given graph?
DSA Python
def articulation_points(graph): time = 0 visited = set() disc = {} low = {} parent = {} ap = set() def dfs(u): nonlocal time visited.add(u) disc[u] = time low[u] = time time += 1 children = 0 for v in graph[u]: if v not in visited: parent[v] = u children += 1 dfs(v) low[u] = min(low[u], low[v]) if u not in parent and children > 1: ap.add(u) if u in parent and low[v] >= disc[u]: ap.add(u) elif v != parent.get(u, None): low[u] = min(low[u], disc[v]) for vertex in graph: if vertex not in visited: dfs(vertex) return sorted(ap) graph = { 0: [1, 2], 1: [0, 2], 2: [0, 1, 3, 5], 3: [2, 4], 4: [3], 5: [2, 6, 7], 6: [5, 7], 7: [5, 6] } print(articulation_points(graph))
Attempts:
2 left
💡 Hint
Look for vertices that, when removed, increase the number of connected components.
✗ Incorrect
Vertices 2, 3, and 5 are articulation points because removing any of them disconnects parts of the graph.
🧠 Conceptual
intermediate1:30remaining
Understanding articulation points in a graph
Which of the following statements about articulation points in an undirected graph is TRUE?
Attempts:
2 left
💡 Hint
Think about the effect of removing a vertex on graph connectivity.
✗ Incorrect
Articulation points are vertices whose removal disconnects the graph into more components.
🔧 Debug
advanced2:00remaining
Identify the error in articulation points code snippet
What error will the following code produce when run on a connected graph?
```python
def find_ap(graph):
time = 0
visited = set()
disc = {}
low = {}
parent = {}
ap = set()
def dfs(u):
visited.add(u)
disc[u] = time
low[u] = time
time += 1
children = 0
for v in graph[u]:
if v not in visited:
parent[v] = u
children += 1
dfs(v)
low[u] = min(low[u], low[v])
if u not in parent and children > 1:
ap.add(u)
if u in parent and low[v] >= disc[u]:
ap.add(u)
elif v != parent.get(u, None):
low[u] = min(low[u], disc[v])
for vertex in graph:
if vertex not in visited:
dfs(vertex)
return ap
```
Attempts:
2 left
💡 Hint
Check how the variable 'time' is modified inside the nested function.
✗ Incorrect
The variable 'time' is assigned inside dfs without declaring it nonlocal, causing UnboundLocalError.
❓ Predict Output
advanced2:00remaining
Output of articulation points on a disconnected graph
What is the output of the code below that finds articulation points in a disconnected graph?
DSA Python
graph = {
0: [1],
1: [0, 2],
2: [1],
3: [4],
4: [3, 5, 6],
5: [4],
6: [4]
}
print(articulation_points(graph))
# articulation_points function is same as in challenge c1Attempts:
2 left
💡 Hint
Check articulation points in each connected component separately.
✗ Incorrect
Vertices 1 and 4 are articulation points separating their respective components.
🧠 Conceptual
expert2:30remaining
Articulation points and bridge edges relationship
Which statement correctly describes the relationship between articulation points and bridge edges in an undirected graph?
Attempts:
2 left
💡 Hint
Think about how removing a bridge edge affects connectivity and which vertices are articulation points.
✗ Incorrect
A bridge edge connects two parts of a graph; removing it increases components. It connects to exactly one articulation point because the other vertex may not disconnect the graph if removed.