Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 36 ยท Connectivity and Paths

Connected Components and Cuts

Find connected components with BFS and union-find, locate bridges and articulation points with a DFS low-link algorithm, and compute strongly connected components in directed graphs.

A network can fall apart. Servers fail, roads close, friendships end. This lesson shows how to find the separate pieces of a graph (components), the single points of failure that would split it (bridges and cut vertices), and how connectivity works in directed graphs (strongly connected components).

Connected components

A connected component of an undirected graph is a maximal set of vertices in which every two are connected by a path. Every vertex lies in exactly one component. A graph is connected exactly when it has one component.

The simplest algorithm: for every vertex not yet visited, run BFS or DFS and give everything it reaches the same label. Total work is O(n + m).

Python Components by repeated BFS

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Union-find (disjoint sets)

When edges arrive one at a time, union-find merges components incrementally. It supports find(x) (which component?) and union(a, b) (merge two) in nearly constant time with two tricks: path compression and union by size. It also powers Kruskal's algorithm in the minimum spanning tree lesson.

Python Union-find

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Bridges and cut vertices

A bridge (cut edge) is an edge whose removal increases the number of components. A cut vertex (articulation point) is a vertex whose removal does. These are the single points of failure of a network.

graph LR
  a --- b
  b --- c
  c --- a
  c --- d
  d --- e
  e --- f
  f --- d

The edge c-d is a bridge, and c and d are cut vertices: remove any of them and the two triangles separate.

A famous O(n + m) method uses DFS with low-link values. For each vertex u record disc[u] (discovery time) and low[u], the earliest discovery time reachable from the subtree of u using any number of tree edges and at most one back edge. Then:

  • A tree edge u-v (child v) is a bridge if low[v] > disc[u]: nothing in v's subtree climbs back to u or above.
  • A vertex u is a cut vertex if it is a non-root with a child v having low[v] >= disc[u], or it is the root with two or more DFS children.
Python Bridges and articulation points

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Graphs with no cut vertex (and at least 3 vertices) are called 2-connected or biconnected: they survive the loss of any single vertex. This is a standard goal for resilient networks.

Strongly connected components

In a directed graph, "connected" splits in two. Two vertices are strongly connected if each can reach the other. The strongly connected components (SCCs) partition the vertices into maximal groups of mutual reachability. Collapse each SCC into a single vertex and the result is always a DAG.

Kosaraju's algorithm finds them with two DFS passes:

  1. Run DFS on G and record vertices by finish time.
  2. Reverse every arc (see reverse() in Building a Graph Class).
  3. Process vertices in decreasing finish time; each DFS in the reversed graph collects exactly one SCC.
Python Kosaraju's SCC algorithm

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

SCCs are used to analyze web link structure, find mutually dependent modules and simplify problems on directed graphs.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is a bridge?

    Removing a bridge increases the number of components. A bridge can never lie on a cycle.
  2. 2. A tree edge u-v (v a child) is a bridge when:

    low[v] > disc[u] means nothing in v's subtree can reach u or above except through this edge.
  3. 3. Two vertices of a directed graph are strongly connected if:

    Strong connectivity needs paths in both directions.
  4. 4. Which data structure merges components in nearly constant amortized time?

    Union-find (disjoint sets) supports find and union in inverse-Ackermann amortized time.

Summary

  • Components are found with repeated BFS or DFS in O(n + m), or incrementally with union-find.
  • Bridges and cut vertices are single points of failure; DFS low-link values find them in O(n + m).
  • Graphs without cut vertices are 2-connected.
  • Directed graphs have strongly connected components, found with Kosaraju's two-pass DFS.
  • Contracting SCCs yields a DAG.

Next: Dijkstra and Shortest Paths