11.11 Dynamic Connectivity Overview

Problem

Offline connectivity works well when edges are fixed, or when all updates can be processed in a convenient order. Real systems are messier. Networks gain and lose links. Roads close. Machines fail. Social connections appear and disappear. A graph changes over time, and we still need to answer questions such as:

Are u and v connected right now?

This is the dynamic connectivity problem.

The difficulty comes from deletion. Adding an edge is easy with union-find. Removing an edge may split a component, and ordinary union-find has no operation for undoing a merge.

Solution

Dynamic connectivity problems fall into three main classes:

Problem type	Updates allowed	Typical tool
Incremental connectivity	Edge additions only	Union-find
Decremental connectivity	Edge deletions only	Specialized graph structures
Fully dynamic connectivity	Additions and deletions	Dynamic trees, offline rollback, or advanced data structures

The practical lesson is simple: use the weakest model that fits the problem. Incremental connectivity is easy. Fully dynamic connectivity is substantially harder.

Incremental Connectivity

In incremental connectivity, edges are only added.

Example:

add(A,B)
query(A,C)
add(B,C)
query(A,C)

Use union-find directly.

make_set(v) for every vertex

for each operation:
    if operation is add(u,v):
        union(u,v)

    if operation is query(u,v):
        answer find(u) == find(v)

This gives nearly constant amortized time per operation.

Example

Start with:

A   B   C   D

Operation:

add(A,B)

Components:

{A,B}   {C}   {D}

Query:

connected(A,C)

Answer:

false

Operation:

add(B,C)

Components:

{A,B,C}   {D}

Query:

connected(A,C)

Answer:

true

Union-find handles this perfectly because components only merge. They never split.

Why Deletion Is Hard

Now consider:

A -- B -- C

The graph has one component:

{A,B,C}

Delete:

remove(B,C)

The graph becomes:

A -- B    C

Components are now:

{A,B}
{C}

Union-find cannot represent this change efficiently because it previously merged all three vertices into one set. The merge has destroyed the information needed to split the component again.

This is the core obstacle in dynamic connectivity.

Decremental Connectivity

In decremental connectivity, edges are only removed.

A simple but expensive approach is:

after every deletion:
    rebuild connected components with DFS/BFS

This costs:

O(V + E)

per deletion.

For small graphs, this is acceptable. For large graphs, it is usually too slow.

More advanced decremental algorithms maintain additional structure so that deletions can be processed faster, but they are more complex and rarely needed in ordinary application code unless graph updates dominate runtime.

Fully Dynamic Connectivity

Fully dynamic connectivity allows both:

add(u,v)
remove(u,v)
query(u,v)

This is the hardest form.

A general fully dynamic solution must support component merges and component splits. Ordinary union-find supports only merges.

There are several approaches:

Approach	Idea	When to use
Rebuild after updates	Recompute components periodically	Small graphs or rare updates
Offline rollback DSU	Process known update intervals with undoable union-find	All operations known in advance
Euler tour trees	Maintain dynamic forests	Advanced online dynamic graphs
Link-cut trees	Maintain forest connectivity with path operations	Advanced tree-heavy workloads
Holm-De Lichtenberg-Thorup style structures	Maintain fully dynamic connectivity with levels	Research-grade or library-grade systems

For a cookbook implementation, the first two are the most practical.

Practical Strategy 1: Rebuild Periodically

If updates are rare and queries are frequent, rebuild connected components after a batch of updates.

pending_updates = []

for each operation:
    if update:
        store update
        mark graph dirty

    if query:
        if graph dirty and pending_updates is large:
            rebuild components
            clear dirty flag

        answer query

This strategy trades strict optimality for simple, reliable code.

It works well when graphs are moderate in size and engineering clarity matters more than asymptotic sophistication.

Practical Strategy 2: Offline Rollback DSU

If all operations are known in advance, deletions can be converted into time intervals.

Suppose an edge exists from time:

start

to time:

end

Instead of deleting the edge directly, we say:

edge is active over [start, end)

Then we process these intervals using a segment tree over time.

At each segment tree node, add the edges active throughout that time interval. Use DSU with rollback so that temporary unions can be undone after returning from recursion.

This technique answers fully dynamic connectivity queries offline.

Rollback DSU Idea

Normal union-find mutates parent pointers permanently.

Rollback DSU records enough information to undo each union.

Before union:

save old parent
save old size or rank

After finishing a recursive branch:

restore old parent
restore old size or rank

The data structure behaves like a stack of changes.

snapshot = current history size
union(a,b)
union(c,d)

rollback(snapshot)

After rollback, the DSU returns to its previous state.

Important Implementation Note

Rollback DSU usually avoids path compression.

Path compression changes many parent pointers during find(), making rollback expensive.

Instead, rollback DSU uses union by size or rank only. This gives:

O(log V)

worst-case find depth, which is acceptable for offline dynamic connectivity.

This is a common tradeoff:

DSU variant	Path compression	Rollback friendly
Standard DSU	Yes	No
Rollback DSU	Usually no	Yes

Example: Offline Dynamic Connectivity

Operations:

1: add(A,B)
2: add(B,C)
3: query(A,C)
4: remove(B,C)
5: query(A,C)

Edge active intervals:

Edge	Active interval
A-B	[1, 6)
B-C	[2, 4)

At time 3, both edges are active, so:

A connected to C = true

At time 5, only A-B is active, so:

A connected to C = false

Rollback DSU lets us evaluate these time intervals without permanently applying edges outside their active range.

Choosing an Approach

Use this rule of thumb:

Situation	Recommended method
Only additions	Standard union-find
Fixed graph, many queries	Build components once
Rare deletions	Rebuild components after deletion or batch
Many operations, all known ahead	Offline rollback DSU
Online additions and deletions at scale	Specialized dynamic connectivity structure

Most production code should start with the simplest method that matches the update pattern. Fully dynamic online connectivity is specialized and easy to over-engineer.

Complexity

For incremental connectivity with standard DSU:

Operation	Complexity
Add edge	O(α(V))
Query connectivity	O(α(V))
Space	O(V)

For rebuild-after-deletion:

Operation	Complexity
Deletion	O(1) to mark, O(V+E) when rebuilding
Query	O(α(V)) after rebuild
Space	O(V+E)

For offline rollback DSU with segment tree over time, a typical bound is:

O((M log M) log V)

where M is the number of operations. With careful implementation, the practical cost is often good enough for large offline query batches.

Common Mistakes

Using Standard DSU for Deletions

Once standard DSU merges two components, it cannot split them.

Adding Path Compression to Rollback DSU

Path compression makes many hidden changes. Those changes must also be recorded, which usually defeats the simplicity of rollback.

Treating Online and Offline Problems the Same

If all operations are known in advance, offline algorithms can be much simpler and faster.

Ignoring Edge Multiplicity

If the same edge can be added more than once, track counts or unique edge IDs. Removing one copy may leave another copy active.

Recipe

When facing a dynamic connectivity problem:

1. Classify the update model: incremental, decremental, or fully dynamic.
2. Use standard union-find for additions only.
3. Avoid ordinary union-find when deletions matter.
4. For small or rare-deletion workloads, rebuild components.
5. For offline fully dynamic workloads, use rollback DSU over time intervals.
6. For online high-scale workloads, use a specialized dynamic connectivity structure.

Dynamic connectivity is less about one universal algorithm and more about matching the graph update model to the correct data structure. The next section studies minimum bottleneck spanning trees, a useful MST variant where the goal is to minimize the largest selected edge rather than the total weight.