PK

PKBytes

Explore tracks
Chapter 31: Disjoint Set Union (Union-Find)
31.04Intermediate / Advanced4 topics13 min4 interactive animations

Offline DSU

Union-find only adds, so questions about deletions or limits become easy if you answer them offline, in sorted or reversed order.

Learning goals

  • Answer limited-weight connectivity queries by sorting queries and edges
  • Answer 'connected after t edges?' by processing queries in time order
  • Handle deletions by running time backwards
  • Find the earliest time at which two nodes become connected

Prerequisites

DSU problem patternsSortingOffline queries

A union-find can merge groups but cannot split them. When a problem seems to need splitting, ask whether the questions can be answered in a different order, so that every change becomes a merge.

31.04.1

Sort queries by weight

A typical query is: 'is there a path from a to b using only edges lighter than limit?' Sort the edges by weight and the queries by limit. Process the queries from the smallest limit: before answering a query, add (union) every edge lighter than its limit that has not been added yet. The union-find then represents exactly the allowed edges, and the answer is whether the two ends have the same root. Every edge is added at most once.

Run the preset "Sort queries by limit" (edges 0-1:2 1-2:4 2-3:1 3-4:6, queries 0-3:5 0-4:7 1-3:3): the answers in input order are [true, true, false]. The last query fails because only the edges of weight 2 and 1 are below 3, and they leave 1 and 3 in different sets. The limit is strict: an edge of weight 5 is not below a limit of 5.

Java
1static class DSU {
2    final int[] parent, size;
3    DSU(int n) { parent = new int[n]; size = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } }
4    int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }   // path halving
5    boolean union(int a, int b) {                // false if a and b were already connected
6        int ra = find(a), rb = find(b);
7        if (ra == rb) return false;
8        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
9        parent[rb] = ra; size[ra] += size[rb];
10        return true;
11    }
12}
13
14static boolean[] distanceLimited(int n, int[][] edges, int[][] queries) {      // edges {a, b, w}, queries {a, b, limit}
15    int[][] es = edges.clone();
16    Arrays.sort(es, Comparator.comparingInt(e -> e[2]));
17    Integer[] order = new Integer[queries.length];
18    for (int i = 0; i < order.length; i++) order[i] = i;
19    Arrays.sort(order, Comparator.comparingInt(i -> queries[i][2]));        // lightest limit first
20    DSU d = new DSU(n);
21    boolean[] ans = new boolean[queries.length];
22    int next = 0;
23    for (int qi : order) {
24        while (next < es.length && es[next][2] < queries[qi][2]) { d.union(es[next][0], es[next][1]); next++; }   // activate lighter edges
25        ans[qi] = d.find(queries[qi][0]) == d.find(queries[qi][1]);
26    }
27    return ans;
28}

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

Interactive · edit the input

Your input

Try

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

0
1
2
3
4
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

4

queries

3

No condition evaluated on this step
Execution trace (dry run table)Show 9 steps
StepLineStateWhat happens
1L2edges=4 queries=3Answering 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.
2L8edge=2-3:1 limit=3 components=4Edge 2-3 (weight 1) is lighter than the limit 3 of query 3: activate it.
3L8edge=0-1:2 limit=3 components=3Edge 0-1 (weight 2) is lighter than the limit 3 of query 3: activate it.
4L9query=1-3:3 #=3 connected=falseQuery 3: are 1 and 3 connected using only edges lighter than 3? No: different sets.
5L8edge=1-2:4 limit=5 components=2Edge 1-2 (weight 4) is lighter than the limit 5 of query 1: activate it.
6L9query=0-3:5 #=1 connected=trueQuery 1: are 0 and 3 connected using only edges lighter than 5? Yes: same set.
7L8edge=3-4:6 limit=7 components=1Edge 3-4 (weight 6) is lighter than the limit 7 of query 2: activate it.
8L9query=0-4:7 #=2 connected=trueQuery 2: are 0 and 4 connected using only edges lighter than 7? Yes: same set.
9L11return=[true, true, false]Answers in input order: [true, true, false]. Cost O((E + Q) log) for sorting plus near-constant union-find steps.
31.04.2

Offline connectivity

Another common form: edges arrive over time, and a query asks whether a and b are connected after the first t edges. Sort the queries by t and sweep: add edges one by one, and answer every query whose t has been reached. This is the same sweep as before with the edge index as the sort key instead of the weight.

If edges have timestamps instead of indices, sort them by time first. Because a union-find never forgets, the answer for a later time includes all earlier edges, which is exactly what 'connected after time t' means. Online, without sorting, a union-find can only answer for the latest time.

Java
1static class DSU {
2    final int[] parent, size;
3    DSU(int n) { parent = new int[n]; size = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } }
4    int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }   // path halving
5    boolean union(int a, int b) {                // false if a and b were already connected
6        int ra = find(a), rb = find(b);
7        if (ra == rb) return false;
8        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
9        parent[rb] = ra; size[ra] += size[rb];
10        return true;
11    }
12}
13
14static boolean[] connectedAtTime(int n, int[][] edges, int[][] queries) {     // edges {a, b}, queries {a, b, t}: connected using the first t edges?
15    Integer[] order = new Integer[queries.length];
16    for (int i = 0; i < order.length; i++) order[i] = i;
17    Arrays.sort(order, Comparator.comparingInt(i -> queries[i][2]));
18    DSU d = new DSU(n);
19    boolean[] ans = new boolean[queries.length];
20    int added = 0;
21    for (int qi : order) {
22        while (added < queries[qi][2] && added < edges.length) { d.union(edges[added][0], edges[added][1]); added++; }
23        ans[qi] = d.find(queries[qi][0]) == d.find(queries[qi][1]);
24    }
25    return ans;
26}

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

Interactive · edit the input

Your input

Try

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

0
1
2
3
4
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

4

queries

3

No condition evaluated on this step
Execution trace (dry run table)Show 9 steps
StepLineStateWhat happens
1L2edges=4 queries=3Answering 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.
2L8edge=2-3:1 limit=3 components=4Edge 2-3 (weight 1) is lighter than the limit 3 of query 3: activate it.
3L8edge=0-1:2 limit=3 components=3Edge 0-1 (weight 2) is lighter than the limit 3 of query 3: activate it.
4L9query=1-3:3 #=3 connected=falseQuery 3: are 1 and 3 connected using only edges lighter than 3? No: different sets.
5L8edge=1-2:4 limit=5 components=2Edge 1-2 (weight 4) is lighter than the limit 5 of query 1: activate it.
6L9query=0-3:5 #=1 connected=trueQuery 1: are 0 and 3 connected using only edges lighter than 5? Yes: same set.
7L8edge=3-4:6 limit=7 components=1Edge 3-4 (weight 6) is lighter than the limit 7 of query 2: activate it.
8L9query=0-4:7 #=2 connected=trueQuery 2: are 0 and 4 connected using only edges lighter than 7? Yes: same set.
9L11return=[true, true, false]Answers in input order: [true, true, false]. Cost O((E + Q) log) for sorting plus near-constant union-find steps.
31.04.3

Reverse-delete processing

A union-find cannot delete an edge. But if a problem deletes edges one by one and asks for the number of components after each deletion, run it **backwards**: start with all the edges deleted (every vertex alone) and re-insert the edges from the last deletion to the first. The component count just before each re-insertion is the answer for that deletion. Every operation is now a union.

In the preset "Reverse deletions" (5 vertices on a cycle 0-1 1-2 2-3 3-4 0-4) the answers after deleting the first 1, 2, 3, 4, 5 edges are [1, 2, 3, 4, 5]: the cycle stays connected after one deletion, then falls apart one piece at a time. The animation shows the edges being re-inserted from the last one.

Java
1static class DSU {
2    final int[] parent, size;
3    DSU(int n) { parent = new int[n]; size = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } }
4    int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }   // path halving
5    boolean union(int a, int b) {                // false if a and b were already connected
6        int ra = find(a), rb = find(b);
7        if (ra == rb) return false;
8        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
9        parent[rb] = ra; size[ra] += size[rb];
10        return true;
11    }
12}
13
14static int[] componentsAfterDeletions(int n, int[][] edges) {         // delete edges[0], edges[1], ... in order
15    int m = edges.length;
16    int[] out = new int[m];
17    DSU d = new DSU(n);
18    int comps = n;
19    for (int i = m - 1; i >= 0; i--) {
20        out[i] = comps;                          // components after deleting edges 0..i
21        if (d.union(edges[i][0], edges[i][1])) comps--;      // run time backwards: re-insert the edge
22    }
23    return out;
24}

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

Interactive · edit the input

Your input

Try

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

0
1
2
3
4
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

4

queries

3

No condition evaluated on this step
Execution trace (dry run table)Show 9 steps
StepLineStateWhat happens
1L2edges=4 queries=3Answering 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.
2L8edge=2-3:1 limit=3 components=4Edge 2-3 (weight 1) is lighter than the limit 3 of query 3: activate it.
3L8edge=0-1:2 limit=3 components=3Edge 0-1 (weight 2) is lighter than the limit 3 of query 3: activate it.
4L9query=1-3:3 #=3 connected=falseQuery 3: are 1 and 3 connected using only edges lighter than 3? No: different sets.
5L8edge=1-2:4 limit=5 components=2Edge 1-2 (weight 4) is lighter than the limit 5 of query 1: activate it.
6L9query=0-3:5 #=1 connected=trueQuery 1: are 0 and 3 connected using only edges lighter than 5? Yes: same set.
7L8edge=3-4:6 limit=7 components=1Edge 3-4 (weight 6) is lighter than the limit 7 of query 2: activate it.
8L9query=0-4:7 #=2 connected=trueQuery 2: are 0 and 4 connected using only edges lighter than 7? Yes: same set.
9L11return=[true, true, false]Answers in input order: [true, true, false]. Cost O((E + Q) log) for sorting plus near-constant union-find steps.
31.04.4

Edge activation

When each edge becomes available at some time (a bridge opens on day 5, a road is built in year 12), the earliest time at which two nodes become connected is found by activating the edges in order of time and stopping as soon as the two nodes share a root. The time of the edge that completed the connection is the answer. If all edges are used and the nodes are still apart, they never connect.

This is Kruskal's loop with a different stopping rule, and it shows why sorting by the activation key is the heart of offline union-find: whatever the key (weight, time, index), the sorted sweep keeps the structure equal to 'all edges so far'. The same sweep with a binary search on the answer would work too, but needs a graph search per guess.

Java
1static class DSU {
2    final int[] parent, size;
3    DSU(int n) { parent = new int[n]; size = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } }
4    int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }   // path halving
5    boolean union(int a, int b) {                // false if a and b were already connected
6        int ra = find(a), rb = find(b);
7        if (ra == rb) return false;
8        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
9        parent[rb] = ra; size[ra] += size[rb];
10        return true;
11    }
12}
13
14static int earliestConnection(int n, int[][] edges, int a, int b) {      // edges {u, v, time}; -1 if never connected
15    if (a == b) return 0;
16    int[][] es = edges.clone();
17    Arrays.sort(es, Comparator.comparingInt(e -> e[2]));
18    DSU d = new DSU(n);
19    for (int[] e : es) {
20        d.union(e[0], e[1]);
21        if (d.find(a) == d.find(b)) return e[2];             // this edge completed the connection
22    }
23    return -1;
24}

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

Interactive · edit the input

Your input

Try

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

0
1
2
3
4
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

4

queries

3

No condition evaluated on this step
Execution trace (dry run table)Show 9 steps
StepLineStateWhat happens
1L2edges=4 queries=3Answering 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.
2L8edge=2-3:1 limit=3 components=4Edge 2-3 (weight 1) is lighter than the limit 3 of query 3: activate it.
3L8edge=0-1:2 limit=3 components=3Edge 0-1 (weight 2) is lighter than the limit 3 of query 3: activate it.
4L9query=1-3:3 #=3 connected=falseQuery 3: are 1 and 3 connected using only edges lighter than 3? No: different sets.
5L8edge=1-2:4 limit=5 components=2Edge 1-2 (weight 4) is lighter than the limit 5 of query 1: activate it.
6L9query=0-3:5 #=1 connected=trueQuery 1: are 0 and 3 connected using only edges lighter than 5? Yes: same set.
7L8edge=3-4:6 limit=7 components=1Edge 3-4 (weight 6) is lighter than the limit 7 of query 2: activate it.
8L9query=0-4:7 #=2 connected=trueQuery 2: are 0 and 4 connected using only edges lighter than 7? Yes: same set.
9L11return=[true, true, false]Answers in input order: [true, true, false]. Cost O((E + Q) log) for sorting plus near-constant union-find steps.

Practice ladder

Now try it yourself

Easy

  • Find if Path Exists in Graph

Medium

  • Checking Existence of Edge Length Limited Paths
  • The Earliest Moment When Everyone Become Friends

Advanced

  • Remove Max Number of Edges to Keep Graph Fully Traversable
  • Number of Islands II
  • Bricks Falling When Hit

Key takeaways

  • Sort queries and edges by the same key so that the union-find always equals 'all edges allowed so far'.
  • Deletions become insertions when time runs backwards.
  • The earliest connection time is the time of the edge whose union first joins the two nodes.