Skip to content
TheChatArchiveThe Chat Archive
GPT 5.1· openaiHugging Face Frontier Reasoning Traces

Develop an algorithm to find articulation points in a graph.

  1. User

    Develop an algorithm to find articulation points in a graph.

  2. 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 of u in DFS.
    • low[u]: the earliest (minimum) discovery time reachable from u by:
      • going down zero or more tree edges, then
      • optionally using one back edge.
    • parent[u]: parent of u in DFS tree (or NIL if root).
    • ap[u]: boolean flag indicating whether u is an articulation point.

    Rules to mark articulation points:

    1. 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.
    2. Non-root vertex u:

      • u is an articulation point if it has a child v for which:
        • low[v] >= disc[u]
      • Intuition: v and its descendants cannot reach an ancestor of u (or u itself via a back edge that jumps above u). Removing u disconnects that subtree.

    DFS-based algorithm (Tarjan)

    Assume the graph is undirected, with vertices labeled 0..V-1 and adjacency list adj[u].

    Data structures

    • visited[0..V-1]: boolean
    • disc[0..V-1]: integer
    • low[0..V-1]: integer
    • parent[0..V-1]: integer (initialize to -1)
    • ap[0..V-1]: boolean
    • time: 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] = true
    

    Main 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.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.