GPT 5.1· openai
Frontier Reasoning Traces
Develop an algorithm to find articulation points in a graph.
- User
Develop an algorithm to find articulation points in a graph.
- Assistant
None An articulation point (or cut vertex) in an undirected graph is a vertex whose removal (with its incident edges) increases the number of connected components.
A standard way to find all articulation points is using a single DFS based on discovery times and low values (Tarjan’s algorithm).
Key ideas
For each vertex
u, we keep:disc[u]: the discovery time ofuin DFS.low[u]: the earliest (minimum) discovery time reachable fromuby:- going down zero or more tree edges, then
- optionally using one back edge.
parent[u]: parent ofuin DFS tree (orNILif root).ap[u]: boolean flag indicating whetheruis an articulation point.
Rules to mark articulation points:
-
Root of DFS tree:
- A root vertex
r(i.e.,parent[r] = NIL) is an articulation point if and only if it has two or more children in the DFS tree.
- A root vertex
-
Non-root vertex
u:uis an articulation point if it has a childvfor which:low[v] >= disc[u]
- Intuition:
vand its descendants cannot reach an ancestor ofu(oruitself via a back edge that jumps aboveu). Removingudisconnects that subtree.
DFS-based algorithm (Tarjan)
Assume the graph is undirected, with vertices labeled
0..V-1and adjacency listadj[u].Data structures
visited[0..V-1]: booleandisc[0..V-1]: integerlow[0..V-1]: integerparent[0..V-1]: integer (initialize to-1)ap[0..V-1]: booleantime: global integer counter, starts at 0
DFS procedure
procedure AP_DFS(u): visited[u] = true time = time + 1 disc[u] = time low[u] = time children = 0 // count of children in DFS tree for each v in adj[u]: if not visited[v]: parent[v] = u children = children + 1 AP_DFS(v) // After DFS of v, update low[u] low[u] = min(low[u], low[v]) // Articulation rule for non-root vertices: if parent[u] != -1 and low[v] >= disc[u]: ap[u] = true else if v != parent[u]: // Back edge (u, v) → update low[u] low[u] = min(low[u], disc[v]) // Articulation rule for root: if parent[u] == -1 and children > 1: ap[u] = trueMain driver
procedure FindArticulationPoints(V, adj): for u from 0 to V-1: visited[u] = false parent[u] = -1 ap[u] = false time = 0 // Handle possible disconnected graph: for u from 0 to V-1: if not visited[u]: AP_DFS(u) // Now all articulation points are those with ap[u] = true result = empty list for u from 0 to V-1: if ap[u]: append u to result return result
Complexity
- Each vertex is visited once and each edge is considered at most twice (once from each endpoint).
- Time complexity: O(V + E)
- Space complexity: O(V) for the auxiliary arrays plus storage for the graph.
Notes & extensions
- The algorithm assumes an undirected graph. For directed graphs, articulation points are not defined in the same way; instead, use strongly connected components or dominator trees.
- It naturally handles disconnected graphs by running DFS from each unvisited vertex in the main loop.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.