36.05Intermediate / Advanced3 topics13 min3 interactive animations

Connectivity under changes

Connectivity questions when the graph changes: answer them offline by sorting edges and queries together, use union-find with weight thresholds, and see what dynamic connectivity with deletions requires.

Learning goals

Answer many connectivity queries offline in one sweep
Answer 'connected using edges lighter than a limit' with sorted thresholds
Explain why deletions are harder than additions

Prerequisites

Union-findKruskal's algorithm

Union-find handles edges that only get added. But often the question is: were these two connected at time t? or using only cheap edges? Sorting the questions turns them into a single sweep.

36.05.1

Offline connectivity

When all queries are known in advance (**offline**), sort the edges by the time they appear and the queries by their time. Sweep through the queries; before answering a query at time t, add every edge with time at most t to a union-find. The answer is whether the two vertices have the same root.

The answers are reported in the original query order by remembering each query's index. Total cost: sorting O((m + q) log(m + q)) plus near-constant union-find work. The offline union-find animation shows the same sweep with weight limits.

Java

1static boolean[] connectedByTime(int n, int[][] edges, int[][] queries) {   // edges {a, b, time}; queries {a, b, time}
2    Integer[] eo = new Integer[edges.length], qo = new Integer[queries.length];
3    for (int i = 0; i < eo.length; i++) eo[i] = i;
4    for (int i = 0; i < qo.length; i++) qo[i] = i;
5    Arrays.sort(eo, Comparator.comparingInt(i -> edges[i][2]));
6    Arrays.sort(qo, Comparator.comparingInt(i -> queries[i][2]));
7    int[] parent = new int[n];
8    for (int i = 0; i < n; i++) parent[i] = i;
9    boolean[] answer = new boolean[queries.length];
10    int next = 0;
11    for (int q : qo) {
12        while (next < eo.length && edges[eo[next]][2] <= queries[q][2]) {      // every edge that exists by time t
13            int e = eo[next++];
14            parent[find(parent, edges[e][0])] = find(parent, edges[e][1]);
15        }
16        answer[q] = find(parent, queries[q][0]) == find(parent, queries[q][1]);
17    }
18    return answer;
19}
20static int find(int[] p, int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }

Offline union-find: sort queries by weight, run deletions backwards

Interactive · edit the input

disjoint-set forest (arrow = parent, roots on top) · 5 nodes

Edge activated / query trueCurrentWaitingQuery falseA root

edges sorted by weight (a-b:w)

2-3:11

0-1:22

1-2:43

3-4:64

queries sorted by limit (a-b:limit)

1-3:31

0-3:52

0-4:73

Setup

Answering each query by searching the graph would be slow. Offline, sort both lists: process queries by increasing limit and activate (union) every edge lighter than the limit first. The union-find then already describes exactly the allowed edges, and each edge is added once overall.

Step 1 / 9

Java

1boolean[] distanceLimited(int n, int[][] edges, int[][] queries) {      // edges {a, b, w}, queries {a, b, limit}
2    int[][] es = edges.clone(); Arrays.sort(es, Comparator.comparingInt(e -> e[2]));
3    Integer[] order = new Integer[queries.length];
4    for (int i = 0; i < order.length; i++) order[i] = i;
5    Arrays.sort(order, Comparator.comparingInt(i -> queries[i][2]));    // lightest limit first
6    DSU d = new DSU(n); boolean[] ans = new boolean[queries.length];
7    int next = 0;
8    for (int qi : order) {
9        while (next < es.length && es[next][2] < queries[qi][2]) { d.union(es[next][0], es[next][1]); next++; }   // activate every lighter edge
10        ans[qi] = d.find(queries[qi][0]) == d.find(queries[qi][1]);
11    }
12    return ans;
13}
14int[] componentsAfterDeletions(int n, int[][] edges) {                  // delete edges[0], edges[1], ... in order
15    int m = edges.length; int[] out = new int[m];
16    DSU d = new DSU(n); int comps = n;
17    for (int i = m - 1; i >= 0; i--) {
18        out[i] = comps;                          // components after deleting edges 0..i
19        if (d.union(edges[i][0], edges[i][1])) comps--;                 // run time backwards: re-insert the edge
20    }
21    return out;
22}

Live state

0 unions5 components

edges

queries

No condition evaluated on this step

Execution trace (dry run table)Show 9 steps

Step	Line	State	What happens
1	L2	edges=4 queries=3	Answering each query by searching the graph would be slow. Offline, sort both lists: process queries by increasing limit and activate (union) every edge lighter than the limit first. The union-find then already describes exactly the allowed edges, and each edge is added once overall.
2	L8	edge=2-3:1 limit=3 components=4	Edge 2-3 (weight 1) is lighter than the limit 3 of query 3: activate it.
3	L8	edge=0-1:2 limit=3 components=3	Edge 0-1 (weight 2) is lighter than the limit 3 of query 3: activate it.
4	L9	query=1-3:3 #=3 connected=false	Query 3: are 1 and 3 connected using only edges lighter than 3? No: different sets.
5	L8	edge=1-2:4 limit=5 components=2	Edge 1-2 (weight 4) is lighter than the limit 5 of query 1: activate it.
6	L9	query=0-3:5 #=1 connected=true	Query 1: are 0 and 3 connected using only edges lighter than 5? Yes: same set.
7	L8	edge=3-4:6 limit=7 components=1	Edge 3-4 (weight 6) is lighter than the limit 7 of query 2: activate it.
8	L9	query=0-4:7 #=2 connected=true	Query 2: are 0 and 4 connected using only edges lighter than 7? Yes: same set.
9	L11	return=[true, true, false]	Answers in input order: [true, true, false]. Cost O((E + Q) log) for sorting plus near-constant union-find steps.

36.05.2

Union-find with sorted thresholds

A frequent form: *is there a path between a and b using only edges with weight strictly below limit?* Sort edges by weight and queries by limit, add edges while their weight is below the current limit, and compare roots. This also answers "smallest possible largest edge on a path" by the same logic as Kruskal.

The strictness matters: an edge of weight equal to the limit is **not** allowed. The second preset of the animation, *Limits are strict*, shows an edge of weight 5 not helping a limit of 5.

Java

1static boolean[] connectedBelowLimit(int n, int[][] edges, int[][] queries) {   // edges {a, b, weight}; queries {a, b, limit}
2    Integer[] eo = new Integer[edges.length], qo = new Integer[queries.length];
3    for (int i = 0; i < eo.length; i++) eo[i] = i;
4    for (int i = 0; i < qo.length; i++) qo[i] = i;
5    Arrays.sort(eo, Comparator.comparingInt(i -> edges[i][2]));
6    Arrays.sort(qo, Comparator.comparingInt(i -> queries[i][2]));
7    int[] parent = new int[n];
8    for (int i = 0; i < n; i++) parent[i] = i;
9    boolean[] answer = new boolean[queries.length];
10    int next = 0;
11    for (int q : qo) {
12        while (next < eo.length && edges[eo[next]][2] < queries[q][2]) {       // strictly below the limit
13            int e = eo[next++];
14            parent[find(parent, edges[e][0])] = find(parent, edges[e][1]);
15        }
16        answer[q] = find(parent, queries[q][0]) == find(parent, queries[q][1]);
17    }
18    return answer;
19}
20static int find(int[] p, int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }

Offline union-find: sort queries by weight, run deletions backwards

Interactive · edit the input

disjoint-set forest (arrow = parent, roots on top) · 5 nodes

Edge activated / query trueCurrentWaitingQuery falseA root

edges sorted by weight (a-b:w)

2-3:11

0-1:22

1-2:43

3-4:64

queries sorted by limit (a-b:limit)

1-3:31

0-3:52

0-4:73

Setup

Step 1 / 9

Java

1boolean[] distanceLimited(int n, int[][] edges, int[][] queries) {      // edges {a, b, w}, queries {a, b, limit}
2    int[][] es = edges.clone(); Arrays.sort(es, Comparator.comparingInt(e -> e[2]));
3    Integer[] order = new Integer[queries.length];
4    for (int i = 0; i < order.length; i++) order[i] = i;
5    Arrays.sort(order, Comparator.comparingInt(i -> queries[i][2]));    // lightest limit first
6    DSU d = new DSU(n); boolean[] ans = new boolean[queries.length];
7    int next = 0;
8    for (int qi : order) {
9        while (next < es.length && es[next][2] < queries[qi][2]) { d.union(es[next][0], es[next][1]); next++; }   // activate every lighter edge
10        ans[qi] = d.find(queries[qi][0]) == d.find(queries[qi][1]);
11    }
12    return ans;
13}
14int[] componentsAfterDeletions(int n, int[][] edges) {                  // delete edges[0], edges[1], ... in order
15    int m = edges.length; int[] out = new int[m];
16    DSU d = new DSU(n); int comps = n;
17    for (int i = m - 1; i >= 0; i--) {
18        out[i] = comps;                          // components after deleting edges 0..i
19        if (d.union(edges[i][0], edges[i][1])) comps--;                 // run time backwards: re-insert the edge
20    }
21    return out;
22}

Live state

0 unions5 components

edges

queries

No condition evaluated on this step

Execution trace (dry run table)Show 9 steps

Step	Line	State	What happens
1	L2	edges=4 queries=3	Answering each query by searching the graph would be slow. Offline, sort both lists: process queries by increasing limit and activate (union) every edge lighter than the limit first. The union-find then already describes exactly the allowed edges, and each edge is added once overall.
2	L8	edge=2-3:1 limit=3 components=4	Edge 2-3 (weight 1) is lighter than the limit 3 of query 3: activate it.
3	L8	edge=0-1:2 limit=3 components=3	Edge 0-1 (weight 2) is lighter than the limit 3 of query 3: activate it.
4	L9	query=1-3:3 #=3 connected=false	Query 3: are 1 and 3 connected using only edges lighter than 3? No: different sets.
5	L8	edge=1-2:4 limit=5 components=2	Edge 1-2 (weight 4) is lighter than the limit 5 of query 1: activate it.
6	L9	query=0-3:5 #=1 connected=true	Query 1: are 0 and 3 connected using only edges lighter than 5? Yes: same set.
7	L8	edge=3-4:6 limit=7 components=1	Edge 3-4 (weight 6) is lighter than the limit 7 of query 2: activate it.
8	L9	query=0-4:7 #=2 connected=true	Query 2: are 0 and 4 connected using only edges lighter than 7? Yes: same set.
9	L11	return=[true, true, false]	Answers in input order: [true, true, false]. Cost O((E + Q) log) for sorting plus near-constant union-find steps.

36.05.3

Dynamic connectivity overview

**Dynamic connectivity** allows both edge additions and deletions between queries. Additions are easy: union. Deletions are hard because union-find cannot split a set: removing an edge may or may not disconnect a component, and nothing in the structure says which.

The simplest correct approach rebuilds the union-find from the current edges after any deletion (code below): additions cost almost nothing, a query after a deletion costs O(n + m). Faster methods exist: the **offline** divide-and-conquer over time with a union-find that can roll back, O(m log m log n) (see the rollback animation), and online structures such as link-cut trees or Holm-de Lichtenberg-Thorup with polylogarithmic updates.

Java

1static class DynamicConnectivity {                                   // add and remove edges; queries rebuild lazily after a removal
2    private final int n;
3    private final Map<Long, Integer> count = new HashMap<>();        // multiplicity of each undirected edge
4    private int[] parent;
5    private boolean dirty = true;
6    DynamicConnectivity(int n) { this.n = n; }
7    private long key(int a, int b) { return (long) Math.min(a, b) * n + Math.max(a, b); }
8    void addEdge(int a, int b) {
9        count.merge(key(a, b), 1, Integer::sum);
10        if (!dirty) union(a, b);                                     // an addition never needs a rebuild
11    }
12    void removeEdge(int a, int b) {
13        if (count.merge(key(a, b), -1, Integer::sum) <= 0) count.remove(key(a, b));
14        dirty = true;                                                // a removal may split a component
15    }
16    boolean connected(int a, int b) {
17        if (dirty) rebuild();
18        return find(parent, a) == find(parent, b);
19    }
20    private void rebuild() {
21        parent = new int[n];
22        for (int i = 0; i < n; i++) parent[i] = i;
23        for (long k : count.keySet()) union((int) (k / n), (int) (k % n));
24        dirty = false;
25    }
26    private void union(int a, int b) { parent[find(parent, a)] = find(parent, b); }
27    private static int find(int[] p, int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }
28}

Union-find variants: rollback, parity and weighted (potential) DSU

Interactive · edit the input

forest (no compression, so every union can be undone) · 6 nodes

size 1

Consistent / connectedJust changedConflict or undoneBeing followedA root

parent[x]

history stack (child root → parent root), top last

empty

Setup

A rollback DSU unites by size and never compresses paths, so each union changes exactly one parent and one size. A stack of those changes lets undo() restore the previous state exactly, which is the basis of offline divide-and-conquer on time.

Step 1 / 8

Java

1int[] parent, size; Deque<int[]> history = new ArrayDeque<>();      // each entry {child root, parent root}
2int find(int x) { while (parent[x] != x) x = parent[x]; return x; }     // no path compression: it could not be undone
3boolean union(int a, int b) {
4    int ra = find(a), rb = find(b);
5    if (ra == rb) return false;
6    if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
7    parent[rb] = ra; size[ra] += size[rb];
8    history.push(new int[]{rb, ra});             // remember exactly what changed
9    return true;
10}
11void undo() {
12    int[] h = history.pop();
13    size[h[1]] -= size[h[0]]; parent[h[0]] = h[0];
14}
15int[] parent, parity;                            // parity[x]: 0 if x has the same colour as parent[x], 1 if different
16int find(int x) {                                // returns the root; afterwards parity[x] is relative to it
17    if (parent[x] == x) return x;
18    int p = parent[x], root = find(p);
19    parity[x] ^= parity[p]; parent[x] = root;
20    return root;
21}
22boolean addDifferent(int a, int b) {             // a and b must get different colours; false on conflict
23    int ra = find(a), rb = find(b);
24    if (ra == rb) return parity[a] != parity[b];      // same set: they must already differ
25    parent[ra] = rb; parity[ra] = parity[a] ^ parity[b] ^ 1;
26    return true;
27}
28int[] parent; long[] diff;                       // diff[x] = value[x] - value[parent[x]]
29int find(int x) {
30    if (parent[x] == x) return x;
31    int p = parent[x], root = find(p);
32    diff[x] += diff[p]; parent[x] = root;        // now relative to the root
33    return root;
34}
35boolean addConstraint(int a, int b, long d) {    // value[b] - value[a] == d
36    int ra = find(a), rb = find(b);
37    if (ra == rb) return diff[b] - diff[a] == d;
38    parent[rb] = ra; diff[rb] = diff[a] + d - diff[b];      // value[rb] - value[ra]
39    return true;
40}
41Long query(int a, int b) { return find(a) == find(b) ? diff[b] - diff[a] : null; }

Live state

0 unions0 undos6 components

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L1	n=6	A rollback DSU unites by size and never compresses paths, so each union changes exactly one parent and one size. A stack of those changes lets undo() restore the previous state exactly, which is the basis of offline divide-and-conquer on time.
2	L8	op=0-1 pushed=1→0 components=5	0-1: unite by size: parent[1] = 0, size[0] = 2. Push {1 → 0} on the history.
3	L8	op=2-3 pushed=3→2 components=4	2-3: unite by size: parent[3] = 2, size[2] = 2. Push {3 → 2} on the history.
4	L8	op=1-2 pushed=2→0 components=3	1-2: unite by size: parent[2] = 0, size[0] = 4. Push {2 → 0} on the history.
5	L13	op=undo restored=2 components=4	undo: pop {2 → 0}: 2 becomes a root again and 0 loses its size. The state is exactly as before that union.
6	L8	op=4-5 pushed=5→4 components=3	4-5: unite by size: parent[5] = 4, size[4] = 2. Push {5 → 4} on the history.
7	L2	op=0?3 connected=false	0?3: roots 0 and 2: not connected.
8	L14	return=3 unions=4 undos=1	3 sets remain after 4 unions and 1 undo. Find costs O(log n) without compression, but every change can be reverted.

Practice ladder

Now try it yourself

Easy

Find if Path Exists in Graph

Medium

Number of Provinces
Accounts Merge
Checking Existence of Edge Length Limited Paths

Advanced

Number of Islands II

Key takeaways

Offline: sort edges and queries by time or limit, sweep, and answer with union-find.
A weight limit that is strict excludes edges equal to the limit.
Union-find handles additions only; deletions need a rebuild, offline divide and conquer with rollback, or special structures.