Graph Theory37 sections · 1633 units
Open in Course

Articulation Points - Implementation

(Python with DFS)

Here is the articulation points implementation:

function articulationPoints(n, edges):
    adj = build adjacency list from edges
    disc = array of size n, all -1
    low = array of size n, all -1
    result = empty set
    timer = 0

    function dfs(u, parent):
        disc[u] = timer
        low[u] = timer
        timer = timer + 1
        children = 0

        for v in adj[u]:
            if v == parent:
                continue
            if disc[v] == -1:
                children = children + 1
                dfs(v, u)
                low[u] = min(low[u], low[v])

                // Non-root articulation point
                if parent != -1 and low[v] >= disc[u]:
                    result.add(u)
            else:
                low[u] = min(low[u], disc[v])

        // Root articulation point
        if parent == -1 and children >= 2:
            result.add(u)

    dfs(0, -1)
    return result

Time: O(V+E)O(V + E). Space: O(V)O(V).