Connectivity: Bridges, Articulation Points and Strongly Connected Components

The questions. In an undirected network: a bridge is a link whose loss disconnects it; an articulation point is a node whose loss does. In a directed network (one-way links): a strongly connected component (SCC) is a largest group where every node can reach every other. The three share one technique.

Two numbers per node. During a depth-first search, give each node tin[v], the time it was first reached, and low[v], the earliest tin reachable from its subtree by going down any number of tree edges and then at most one back edge. A back edge is a link to an ancestor that is already on the path.

The bridge rule. After finishing a child v of u, compare low[v] with tin[u]. If low[v] > tin[u], nothing under v can climb back to u or above, so the link u-v is the only connection and is a bridge. Skip the edge you just came along (the parent) when you look for back edges.

def bridges(n, edges):
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    tin, low, timer, found = [-1] * n, [0] * n, [0], []

    def dfs(u, parent):
        tin[u] = low[u] = timer[0]
        timer[0] += 1
        for v in adj[u]:
            if v == parent:
                continue
            if tin[v] != -1:
                low[u] = min(low[u], tin[v])      # a back edge
            else:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > tin[u]:
                    found.append((u, v))
    for s in range(n):
        if tin[s] == -1:
            dfs(s, -1)
    return found

bridges(5, [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4)])   # [(3, 4), (1, 3)]

Reading the example. Nodes 0, 1, 2 form a triangle, so no single link inside it matters. The links 1-3 and 3-4 are the only ways to the rest, so both are bridges. Articulation points use the same numbers with a slightly different test: a non-root u is one if some child has low[v] >= tin[u], and the root is one if it has two or more DFS children.

Strongly connected components (Kosaraju). Run a DFS and note the order in which nodes finish. Build the reverse graph (flip every link). Then take nodes in reverse finishing order and run a DFS on the reversed graph: everything one search reaches is one component. Total work is two passes, O(V + E). Tarjan's version does it in one pass with the same low idea and a stack.

def kosaraju(n, edges):
    adj = [[] for _ in range(n)]
    radj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        radj[b].append(a)
    seen, order = [False] * n, []

    def first(u):
        seen[u] = True
        for v in adj[u]:
            if not seen[v]:
                first(v)
        order.append(u)               # finishing order
    for s in range(n):
        if not seen[s]:
            first(s)

    comp = [-1] * n

    def second(u, c):
        comp[u] = c
        for v in radj[u]:
            if comp[v] == -1:
                second(v, c)
    c = 0
    for u in reversed(order):
        if comp[u] == -1:
            second(u, c)
            c += 1
    return comp

kosaraju(6, [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3)])
# [0, 0, 0, 1, 1, 1]: two loops of three, joined by the one-way link 2 -> 3

Shrink each component to a single node and the result is a graph with no cycles (a DAG), which can be ordered topologically. That is how build tools group packages that depend on each other in a loop.

Where it runs in production. Finding the one switch or link whose failure splits a data center network, spotting circular dependencies between services, detecting deadlocks as cycles in a wait-for graph, and grouping pages that link to each other.