MST, SCC & Connectivity

Shortest Paths & Bipartite Check answers "what's the cheapest way to reach one destination." This page answers the questions about a graph's connective structure instead: what's the cheapest way to connect everything at once (MST), which groups of vertices can all reach each other (SCC), and which single edge or vertex would break the graph apart if it failed (bridges and articulation points).

1. Minimum spanning trees: the cut property

A spanning tree of a connected graph is a subset of its edges that connects every vertex using exactly V - 1 edges and no cycle - a tree, by the definition from Graph Anatomy. A minimum spanning tree (MST) is the spanning tree whose edges sum to the smallest total weight. Both algorithms below build one greedily, and both lean on the same theorem to justify why greedy is even allowed to work here:

The cheapest bridge across any split.

Split the graph's vertices into any two non-empty groups, however you like - call the edges crossing between the groups the "bridges." The cut property says: the single cheapest bridge is always safe to include in some MST. If a cheaper edge existed instead, you could always use it to reconnect the split for less.

Kruskal and Prim are the same theorem applied in two different orders - one sorts every edge in the whole graph up front, the other only ever looks at the bridges out of whatever tree it's already grown.

2. Kruskal's algorithm

Sort every edge by weight, then walk the sorted list adding an edge whenever it connects two vertices that aren't already connected - i.e. whenever it doesn't close a cycle. That "doesn't close a cycle" check is exactly the Union-Find union call from Cycles & Ordering: a union that returns True is a genuinely new bridge; a False means both endpoints were already in the same group, so this edge would only close a cycle and gets skipped.

def kruskal(num_nodes, edges):

# edges = list of (weight, u, v); UnionFind is the class from Cycles & Ordering

uf = UnionFind()

mst_weight, chosen = 0, []

for w, u, v in sorted(edges):

if uf.union(u, v): # True = genuinely new bridge, no cycle closed

mst_weight += w

chosen.append((u, v, w)) # keep the EDGES, not just the total

if len(chosen) == num_nodes - 1:

break # a spanning tree is full at V-1 edges

if len(chosen) < num_nodes - 1:

return None, [] # the graph was disconnected: no spanning tree

return mst_weight, chosen

⚠

A disconnected graph has no spanning tree

A disconnected graph has no spanning tree, and Kruskal will not tell you unless you check. Run it on two separate components and it happily returns the total weight of a spanning forest - a plausible-looking number that answers a different question. The check is one comparison: a spanning tree of V vertices has exactly V - 1 edges, so len(chosen) < num_nodes - 1 means disconnected. The early break at V - 1 is the same fact used as an optimisation.

Solid = in the MST; dashed B-D would only close a cycle.

⚠

Kruskal's cycle check is "same group," not "seen before"

Kruskal's cycle check is "same group already," not "have I seen this edge before." It's tempting to think of the skipped edge as a duplicate - it isn't. B-D is a perfectly real, never-before-seen edge; it's skipped purely because find(B) == find(D) already, via the path A-C-D plus A-B. Any edge whose endpoints already share a leader closes a cycle, full stop, regardless of whether it "looks new."

3. Prim's algorithm

Prim grows a single tree outward from one starting vertex, always adding the cheapest edge that leaves the current tree and lands on a vertex not yet in it - a min-heap keyed on edge weight makes "cheapest available bridge" an O(log E) pop, the same shape as Dijkstra's priority queue.

import heapq

 

def prim(graph, start):

# graph[u] = list of (v, weight)

visited = {start}

pq = [(w, start, v) for v, w in graph[start]]

heapq.heapify(pq)

mst_weight = 0

while pq and len(visited) < len(graph):

w, u, v = heapq.heappop(pq)

if v in visited:

continue # stale entry, v already joined the tree

visited.add(v)

mst_weight += w

for nv, nw in graph[v]:

if nv not in visited:

heapq.heappush(pq, (nw, v, nv))

return mst_weight

⚠

Prim's heap key is edge weight, not cumulative distance

Prim's heap key is the raw edge weight into the tree, never a cumulative distance from the start. That's the entire difference from Dijkstra's loop, which otherwise looks nearly identical - copy Dijkstra's nd = d + w line into Prim by habit and you've silently built a shortest-path tree instead of a minimum spanning tree. A single expensive-but-direct edge can beat a chain of cheap ones for MST purposes; for shortest-path purposes it never can.

Mnemonic

"Kruskal picks the cheapest edge anywhere; Prim picks the cheapest edge at the frontier." Same greedy cut-property justification, opposite scan order

• Kruskal is edge-first (global sort), Prim is vertex-first (local frontier).

4. Strongly connected components: Tarjan's algorithm

A strongly connected component (SCC) of a directed graph is a maximal group of vertices where every vertex can reach every other vertex in the group, following edge directions the whole way. Tarjan's algorithm finds all of them in one DFS pass by tracking, for every vertex, the earliest DFS-discovery time reachable from it without leaving the current DFS stack - its low-link value.

def tarjan_scc(graph, n):

index_counter = [0]

stack = []

on_stack = [False] * n

indices = [None] * n

low = [None] * n

sccs = []

 

def strongconnect(u):

indices[u] = low[u] = index_counter[0]

index_counter[0] += 1

stack.append(u)

on_stack[u] = True

for v in graph[u]:

if indices[v] is None:

strongconnect(v)

low[u] = min(low[u], low[v]) # tree edge: inherit descendant's reach

elif on_stack[v]:

low[u] = min(low[u], indices[v]) # live back edge into the current SCC

if low[u] == indices[u]: # u is the ROOT of its SCC

scc = []

while True:

v = stack.pop()

on_stack[v] = False

scc.append(v)

if v == u:

break

sccs.append(scc)

 

for u in range(n):

if indices[u] is None:

strongconnect(u)

return sccs

⚠

low[u] updates only from vertices still on the stack

Only back edges to vertices still on_stack update low[u] - an edge to an already-popped vertex belongs to a different, already-finished SCC and must be ignored. Miss the on_stack check and a cross edge into a completed component would incorrectly merge two separate SCCs into one. That's the entire reason the algorithm keeps an explicit stack instead of just a plain visited set - on_stack is what distinguishes "still part of my current component" from "a totally different, already-closed one."

5. Strongly connected components: Kosaraju's algorithm

Kosaraju's algorithm reaches the same answer with a different, arguably easier-to-remember trick: run DFS twice, once forward and once on the graph with every edge reversed.

def kosaraju_scc(graph, n):

visited = [False] * n

order = []

 

def dfs1(u):

visited[u] = True

for v in graph[u]:

if not visited[v]:

dfs1(v)

order.append(u) # postorder: u finishes after every descendant

 

for u in range(n):

if not visited[u]:

dfs1(u)

 

reverse_graph = [[] for _ in range(n)]

for u in range(n):

for v in graph[u]:

reverse_graph[v].append(u) # flip every edge

 

visited = [False] * n

sccs = []

 

def dfs2(u, component):

visited[u] = True

component.append(u)

for v in reverse_graph[u]:

if not visited[v]:

dfs2(v, component)

 

for u in reversed(order): # highest finish time first

if not visited[u]:

component = []

dfs2(u, component)

sccs.append(component)

return sccs

Finish times from the first pass rank every SCC relative to the others.

The vertex that finishes last in the first DFS is guaranteed to belong to an SCC with no incoming edges from any not-yet-explored SCC - so starting the second pass there, on the reversed graph, can only wander into its own component, never leak into a different one. Repeating "start from the highest remaining finish time" isolates one SCC at a time.

⚠

Tarjan needs both the reversal and finish-time order

Both halves of the trick are required - the reversal and the finish-time order. Run the second DFS on the original graph instead of the reversed one, or process vertices in the wrong order (lowest finish time first instead of highest), and components silently merge or split incorrectly. Neither mistake throws an error - the output is just wrong, which is what makes this one worth tracing by hand once on a small example before trusting it.

Mnemonic

"Tarjan finds SCCs in one pass with a stack; Kosaraju finds them in two passes with a reversal." Same answer, different trade: Tarjan is more mechanical to hand-trace correctness for (the low/indices invariant is self-contained per call); Kosaraju is easier to remember the shape of (finish times, then flip, then repeat) but needs both DFS passes to be exactly right.

6. Bridges and articulation points

The same disc/low timestamps Tarjan's SCC algorithm uses answer a different, very practical question about undirected graphs: which single part of this network is a single point of failure?

• A bridge (or cut edge) is an edge whose removal increases the number of connected components. It is the only route between the two sides.
• An articulation point (or cut vertex) is a vertex whose removal - along with all its edges - increases the number of components.

A bridge is an edge with no alternative route.

Equivalently: an edge is a bridge exactly when it lies on no cycle. That is the whole theorem, and it is why a tree's every edge is a bridge (a tree has no cycles) and a cycle graph has none at all.

The low value makes "is there an alternative route" computable in one DFS pass. Define low[u] as the smallest disc reachable from u's subtree using tree edges downward plus at most one back edge. Then for a tree edge u -> v:

• low[v] > disc[u] means nothing in v's subtree can reach u or anything above u except through the edge u-v itself. So that edge is a bridge.
• low[v] >= disc[u] is the weaker condition: v's subtree can at best get back to u, never past it. So removing u strands that subtree, and u is an articulation point.

def bridges(num_nodes, adj):

# adj[u] = list of (neighbour, edge_id) - edge ids matter, see the trap below

disc = [-1] * num_nodes

low = [0] * num_nodes

clock, out = [0], []

 

def dfs(u, in_eid):

disc[u] = low[u] = clock[0]

clock[0] += 1

for v, eid in adj[u]:

if eid == in_eid:

continue # never reuse the edge we arrived on

if disc[v] == -1:

dfs(v, eid)

low[u] = min(low[u], low[v]) # inherit the child's reach

if low[v] > disc[u]: # STRICT: no way around this edge

out.append((u, v))

else:

low[u] = min(low[u], disc[v]) # a back edge: reach up to v

for u in range(num_nodes):

if disc[u] == -1:

dfs(u, -1)

return out

def articulation_points(num_nodes, adj):

# adj[u] = list of neighbours (simple graph)

disc = [-1] * num_nodes

low = [0] * num_nodes

is_cut = [False] * num_nodes

clock = [0]

 

def dfs(u, parent):

disc[u] = low[u] = clock[0]

clock[0] += 1

children = 0

for v in adj[u]:

if v == parent:

continue

if disc[v] == -1:

children += 1

dfs(v, u)

low[u] = min(low[u], low[v])

if parent != -1 and low[v] >= disc[u]: # NON-STRICT

is_cut[u] = True

else:

low[u] = min(low[u], disc[v])

if parent == -1 and children > 1: # the root needs its own rule

is_cut[u] = True

for u in range(num_nodes):

if disc[u] == -1:

dfs(u, -1)

return [u for u in range(num_nodes) if is_cut[u]]

⚠

One > vs >= separates two algorithms

One > versus one >= is the entire difference between the two algorithms. low[v] > disc[u] finds bridges; low[v] >= disc[u] finds articulation points. The equality case is the one where v's subtree can loop back to u but no further: the edge u-v is then not a bridge (the loop is an alternative route for the edge), but u is still a cut vertex (the loop goes through u, so removing u kills it too). Getting the comparison backwards produces answers that are right on trees and wrong on everything else.

⚠

The DFS root needs its own articulation rule

The DFS root needs a separate articulation-point rule, and it is easy to forget. The root has no parent, so the low[v] >= disc[u] test is meaningless for it - it would flag every root. The correct test is structural: the root is a cut vertex exactly when it has two or more DFS children, because each child subtree only connects to the others through the root.

⚠

Bridges skip the arriving edge, not the vertex

Bridges must skip the arriving edge, not the arriving vertex. Skipping by parent vertex (if v == parent) silently reports a bridge that isn't one whenever there are parallel edges: two edges between u and v mean neither is a bridge, but vertex-based skipping ignores the second copy and so never finds the back edge that proves it. Carrying an edge id costs one tuple and removes the whole class of bug. Articulation points do not have this problem - a parallel edge cannot change whether a vertex is a cut vertex.

You want	Condition	The problem it solves
Bridge (critical edge)	low[v] > disc[u] on a tree edge	LC 1192 Critical Connections in a Network - "which servers, if the cable between them fails, split the network."
Articulation point (critical vertex)	low[v] >= disc[u], plus the root having 2+ children	"Which single machine going down would partition the cluster."
2-edge-connected components	the components left after deleting every bridge	Contracting each one gives a tree - the bridge tree - which turns path queries on a general graph into path queries on a tree.

Mnemonic

disc is "when I was found"; low is "the highest ancestor my subtree can still see." Every low-link algorithm on this page - Tarjan's SCC, bridges, articulation points - is that one comparison asked slightly differently.

7. The condensation graph: turning any digraph into a DAG

Once you have the SCCs, contract each one into a single vertex and keep an edge between two of them wherever any original edge crossed. The result is the condensation (or component graph), and it is always a DAG.

The proof is one line: if the condensation had a cycle, every SCC on that cycle could reach every other, so they would all have been one SCC to begin with - contradicting maximality.

def condensation(num_nodes, adj, comp_of):

# comp_of[v] = the SCC id of v, from tarjan_scc / kosaraju_scc above

num_comps = max(comp_of) + 1

dag = [set() for _ in range(num_comps)]

for u in range(num_nodes):

for v in adj[u]:

if comp_of[u] != comp_of[v]: # skip edges inside one SCC

dag[comp_of[u]].add(comp_of[v])

return [sorted(s) for s in dag]

Condensation is how a cyclic problem becomes an acyclic one.

Every technique that needs a DAG - topological sort, longest path, counting paths, DP over an ordering - is unavailable on a graph with cycles, and becomes available the moment you condense. "Find the longest chain of mutual-follow groups" is not a DAG problem as stated; it is one after condensing.

⚠

Condensing an SCC loses its size

Condensing loses information you may still need, so keep the size of each component. The condensation vertex for a 5-cycle and the one for a single vertex look identical in the DAG. Problems asking "how many vertices are in the largest reachable set" need size[comp] carried alongside, and the DP is then over component sizes, not over component counts.

Mnemonic

SCC + condense + topological sort is a three-step reduction, and it is worth recognising as one move. Anything of the shape "on a directed graph with cycles, find the best/longest/count-of something along the edges" is this: condense to a DAG, then run the DAG version of the algorithm you already know.

8. 2-SAT: the flagship SCC application

SCCs look like a niche curiosity until you meet 2-SAT, where they turn an apparently exponential search into one linear pass.

The problem. You have boolean variables and a list of constraints, each of which is a clause over exactly two literals: (a OR b). Is there an assignment satisfying all of them? For three literals per clause this is 3-SAT, the canonical NP-complete problem. For two, it is O(V + E).

The reduction. A clause (a OR b) is logically identical to two implications: if a is false then b must be true, and vice versa. So build an implication graph with two vertices per variable - one for the literal and one for its negation - and add two directed edges per clause:

$(a \lor b) \equiv (\lnot a \to b) \land (\lnot b \to a)$

The theorem. The formula is satisfiable iff no variable has its literal and its negation in the same SCC. If they share a component then each implies the other, so x implies NOT x and NOT x implies x - a contradiction with no escape. If they never share one, an assignment always exists, and reading it off is one more line.

def two_sat(num_vars, clauses):

# literal encoding: variable i -> 2i (true), 2i+1 (false); negate with ^ 1

n = 2 * num_vars

adj = [[] for _ in range(n)]

 

def lit(v, is_true):

return 2 * v + (0 if is_true else 1)

 

for (a, a_true), (b, b_true) in clauses:

la, lb = lit(a, a_true), lit(b, b_true)

adj[la ^ 1].append(lb) # NOT a implies b

adj[lb ^ 1].append(la) # NOT b implies a

 

comp = scc_ids(n, adj) # from tarjan_scc / kosaraju_scc above

for v in range(num_vars):

if comp[2 * v] == comp[2 * v + 1]:

return None # a literal and its negation collided

# a variable is TRUE when its true-literal's component comes LATER in

# topological order than its false-literal's

return [comp[2 * v] < comp[2 * v + 1] for v in range(num_vars)]

⚠

SCC numbering direction flips the final comparison

The final comparison depends on how your SCC routine numbers components, and getting it backwards produces a valid-looking but wrong assignment. Tarjan assigns ids in reverse topological order (a sink component gets a low id), so "later in topological order" means a smaller id - hence < above. Kosaraju as written on this page numbers components in forward topological order, so the same rule becomes >. The satisfiability answer is unaffected either way; only the extracted assignment flips. If you are unsure, verify the assignment against the clauses - it is O(clauses) and removes the doubt entirely.

Mnemonic

"Pick the literal whose component is further downstream." Implications flow forward, so the component that nothing else forces is the safe one to make true. That is the whole assignment rule, and it is why the topological order of the condensation (section 7) is the object you actually need.

2-SAT is the boundary of easy.

Two literals per clause reduces to reachability, which is linear. Three literals does not reduce to anything - the implication "if a is false then b OR c" is not a single edge, and there is no graph to build. That one-literal difference is the same cliff as 2-coloring versus 3-coloring on Coloring & Covering, and it is not a coincidence: both are the gap between a constraint that pins one thing and a constraint that offers a choice.

⚠

Every 2-SAT clause needs exactly two literals

Every constraint must be expressible as a two-literal clause, and problems disguise this. "At most one of these three" is fine - it is three pairwise clauses (NOT a OR NOT b). "Exactly one of these three" is not, because "at least one of three" is a three-literal clause. If a constraint needs a genuine three-way choice, 2-SAT does not apply no matter how the problem is phrased.

Where to go next

• Cycles & Ordering - the topological sort that the condensation above unlocks, and the union-find that Kruskal depends on.
• Eulerian & Hamiltonian - the directed Eulerian conditions lean on the strong-connectivity check from this page.