DSU, MST, and offline activation · HTML
Vertices or edges carry keys, and a query depends only on comparing a key with threshold t; sort events and queries so the active set grows one way.
Recognition signals
- Many connectivity queries at different thresholds
- An object stays available after crossing its threshold
- Queries may be processed offline
- Activation only merges neighboring components
- A BFS per query repeats the same scans
False friends
| Signal | Why it is different |
|---|
| Answers must follow real-time arrival | Offline sorting changes processing order; a truly online problem needs another structure. |
| State both enters and leaves | Plain DSU handles monotone activation; non-monotone changes need rollback or divide-and-conquer machinery. |
Core invariant
Before answering threshold t, exactly the qualifying events are active, and DSU components equal the true components under t.
State, transition, and processing order
| Item | Definition |
|---|
| State | Sorted events, indexed queries, DSU, a scan pointer, and active flags in a vertex-activation model. |
| Transition | Advance the threshold, activate and union every newly eligible event, then read the query and store it at its original index. |
| Frontier / order | Everything left of the scan pointer is active, everything right is inactive, and the pointer never retreats. |
Python skeleton
def offline_connectivity(n, edges, queries):
p = list(range(n))
def find(x):
while x != p[x]:
p[x] = p[p[x]]; x = p[x]
return x
def union(a, b):
a, b = find(a), find(b)
if a != b: p[b] = a
edges = sorted(edges) # (weight,u,v)
order = sorted((lim, i, u, v) for i, (lim,u,v) in enumerate(queries))
ans, j = [False] * len(queries), 0
for lim, i, u, v in order:
while j < len(edges) and edges[j][0] <= lim:
_, a, b = edges[j]; union(a, b); j += 1
ans[i] = find(u) == find(v)
return ans
Correctness sketch
- Sorting places all and only events with key<=limit left of the pointer.
- Unioning each active edge makes DSU components match the active subgraph.
- A query only reads that state, so it sees exactly its threshold-defined graph.
- Writing by original index restores the requested output order.
Complexity
| Time | Space | Parameters |
|---|
| O((E+Q) log(E+Q)+(E+Q)α(V)) | O(V+E+Q) | V objects, E activation events, Q queries |
Edge cases
- Strict versus non-strict thresholds change equal-key ordering
- Self-connectivity still matters with no events
- Thresholds may lie outside all keys
- Equal-key events must be handled as a batch
- Duplicate queries retain separate indices
Error patterns
| Pattern | Why it fails / fix |
|---|
| Wrong equal-key tie break | For <=, same-key events must precede the query. |
| Appending in sorted order | Store answers by original query index. |
| Rebuilding DSU per query | That discards the shared-scan advantage. |
Selection and exclusion rules
- Reorderable queries plus a monotonically growing active set: choose offline activation.
- For one query, direct search may be simpler.
- Fix < versus <= before defining event order.
- On vertex activation, union only already-active neighbors.
Original micro-example
| Part | Detail |
|---|
| Result | Threshold 4 contains only the first edge; threshold 5 inserts both tied edges before answering. |
| Scenario | Edges activate at thresholds 2, 5, and 5; connectivity is queried at 4 and 5. |
| Walkthrough | The pointer advances once and every edge is processed once, so both queries reuse prior work. |
Recall prompts
My notes