Articulation Points (Critical Nodes in a Graph)

Connectivity asks whether vertices stay linked after removals—Union-Find for dynamic merges; Tarjan for articulation points and bridges offline.

Why this shows up in the real world

Maps & routing, social networks, and dependency systems are modeled as graphs—vertices are places or tasks, edges are roads or prerequisites.

Core idea (explained for students)

Articulation point: removing node increases component count. Bridge: removing edge disconnects. Bipartite: 2-color BFS/DFS, no odd cycle.

Try this in Python

class UnionFind:
    def __init__(self, n: int) -> None:
        self.p = list(range(n))
        self.r = [0] * n

    def find(self, x: int) -> int:
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]
            x = self.p[x]
        return x

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.r[ra] < self.r[rb]:
            ra, rb = rb, ra
        self.p[rb] = ra
        if self.r[ra] == self.r[rb]:
            self.r[ra] += 1
        return True


uf = UnionFind(5)
uf.union(0, 1)
uf.union(2, 3)
print(uf.find(0), uf.find(3))

Common mistakes

• Checking bridges with only BFS tree edges conflated with back edges.
• Union without path compression (TLE).

Key takeaways

• Offline queries: DSU with rollback or Tarjan once.
• Online merges: Union-Find with union by rank.