Workspace

Problem workspace

3 day streakD

Articulation Points

HardGraphsConnectivity

The challenge

Find vertices in an undirected graph whose removal, together with their incident edges, increases the number of connected components.

The DFS root has a different rule from other vertices. Distinguish DFS children from ordinary graph degree.

Example

C and D are articulation points. Removing C separates D and E from the cycle; removing D isolates E.

Use the walkthrough below to inspect the input and each state change.

See Articulation points, step by step

Follow the edges. Watch the state change.

Undirected · 6 vertices · 6 edgesA = 0, B = 1, …
Connected graphUndirected graph with 6 vertices. Initialize discovery and low-link values. low[u] is the earliest discovery reachable from u’s DFS subtree using tree edges and at most one back edge. Skip the parent edge by ID. The edge list and state table below provide the graph in text.ABCDEF
CurrentVisited / acceptedUnvisited
Discovery / low-link
ABCDEF
——————
Step 01 / 15

Initialize discovery and low-link values.

low[u] is the earliest discovery reachable from u’s DFS subtree using tree edges and at most one back edge. Skip the parent edge by ID.

discovery = [-1] * V; timer = 0

DFS path · top last

Empty
View input edges

A — B · A — F · B — C · C — F · C — D · D — E

Put it into code

A vertex is a cut point when it is the only connection from a DFS child subtree to the rest.

Vertices are numbered 0 to V − 1. C++ uses C++17 or later.

def find_cuts(n, edges):
    # Undirected edges listed ONCE as (u, v).
    # Edge IDs make parallel edges safe.
    adj = [[] for _ in range(n)]
    for edge_id, (u, v) in enumerate(edges):
        adj[u].append((v, edge_id))
        adj[v].append((u, edge_id))
    discovery, low = [-1] * n, [-1] * n
    bridges, articulation = [], set()
    timer = 0

    def visit(u, parent_edge=-1):
        nonlocal timer
        discovery[u] = low[u] = timer
        timer += 1
        children = 0
        for v, edge_id in adj[u]:
            if edge_id == parent_edge:
                continue
            if discovery[v] == -1:
                children += 1
                visit(v, edge_id)
                low[u] = min(low[u], low[v])
                if low[v] > discovery[u]:
                    bridges.append(edge_id)
                if parent_edge != -1 and low[v] >= discovery[u]:
                    articulation.add(u)
            else:
                low[u] = min(low[u], discovery[v])
        if parent_edge == -1 and children > 1:
            articulation.add(u)

    for u in range(n):
        if discovery[u] == -1:
            visit(u)
    return bridges, sorted(articulation)

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap