Graphs and Graph Algorithms Questions

Direct answer

Kruskal's algorithm builds a minimum spanning tree (MST) by sorting all edges by weight ascending, then greedily adding each edge to the MST as long as it does not create a cycle with edges already added, using Union-Find to detect cycles in near-constant time per check. The algorithm stops once $n-1$ edges have been added (a spanning tree on $n$ nodes always has exactly $n-1$ edges), and total runtime is dominated by the sort: $O(E \log E)$, with the Union-Find operations contributing an additional $O(E \cdot \alpha(n))$, which is asymptotically dominated by the sort.

Structured elaboration

Why greedy-by-weight, skip-cycles is correct. This is the cut property in action: for any partition of the nodes into two non-empty sets, the minimum-weight edge crossing that partition must belong to SOME minimum spanning tree. Processing edges in ascending weight order and adding each one that does not close a cycle is exactly equivalent to repeatedly picking the lightest crossing edge for whatever partition the current partial MST implicitly defines (the current set of already-connected components on one "side," everything else on the other), which is why the greedy approach provably produces a GLOBALLY minimum tree, not just a locally reasonable one.

Role of Union-Find. Two nodes already in the same Union-Find set means a path already connects them using edges already accepted into the MST; adding another edge between them would necessarily create a cycle. Checking find(u) != find(v) before accepting an edge is an $O(\alpha(n))$ amortized cycle check, far cheaper than an explicit DFS/BFS cycle check per candidate edge, which is what makes Kruskal's practical at scale.

Sorting complexity dominates. Sorting $E$ edges is $O(E \log E)$. Since $E \le V^2$ for a simple graph (and typically $E = O(V)$ for sparse graphs common in practice), $O(E \log E)$ is also frequently written as $O(E \log V)$ (because $\log(V^2) = 2\log V$, a constant factor difference). The Union-Find operations across all $E$ edges cost $O(E \cdot \alpha(n))$, which is asymptotically smaller than the sort, so the sort is the bottleneck: Kruskal's overall complexity is $O(E \log E)$.

Worked example

from typing import List, Tuple

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y) -> bool:
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True

def kruskal(n: int, edges: List[Tuple[int, int, int]]) -> List[Tuple[int, int, int]]:
    dsu = DSU(n)
    mst = []
    for u, v, w in sorted(edges, key=lambda e: e[2]):
        if dsu.union(u, v):
            mst.append((u, v, w))
            if len(mst) == n - 1:
                break
    return mst

if __name__ == "__main__":
    n = 6
    edges = [
        (0, 1, 4), (0, 2, 4), (1, 2, 2),
        (2, 3, 3), (2, 5, 2), (2, 4, 4), (3, 4, 3), (5, 4, 3), (5, 3, 1)
    ]
    mst = kruskal(n, edges)
    total_weight = sum(w for _, _, w in mst)
    print("MST edges:", mst)
    print("total weight:", total_weight)
    print("edge count:", len(mst), "(expected n-1 =", n - 1, ")")

Output:

MST edges: [(5, 3, 1), (1, 2, 2), (2, 5, 2), (3, 4, 3), (0, 1, 4)]
total weight: 12
edge count: 5 (expected n-1 = 5 )

Trace by hand: edges sorted by weight are (5,3,1), (1,2,2), (2,5,2), (2,3,3), (3,4,3), (5,4,3), (0,1,4), (0,2,4), (2,4,4). Processing in that order: (5,3,1) accepted (new edge, new component {5,3}). (1,2,2) accepted ({1,2}). (2,5,2) accepted, merging {1,2} and {5,3} into {1,2,5,3}. (2,3,3) rejected, 2 and 3 are already in the same component. (3,4,3) accepted ({1,2,5,3,4}). (5,4,3) rejected, same component already. (0,1,4) accepted, merging in node 0, now 5 edges total, stop. Sum: $1+2+2+3+4=12$, matching the printed output exactly.

Trade-offs and pitfalls

• Common mistake: forgetting the early-stop condition. Once $n-1$ edges are accepted, the MST is complete and any further edges are guaranteed to create a cycle if added; continuing to scan the remaining sorted edges (which Union-Find would correctly reject anyway) wastes work, though it does not produce a WRONG answer, only a slower one on a graph where $E \gg V$.
• Kruskal's requires the graph to be CONNECTED to produce a true spanning tree. On a disconnected graph, the algorithm terminates having accepted fewer than $n-1$ edges (once no more cycle-free edges remain to add), producing a minimum spanning FOREST, one tree per connected component, rather than a single tree; a correct implementation should check len(mst) == n - 1 at the end and treat a shortfall as a signal the graph was disconnected, not silently return a forest labeled as a tree.
• Common mistake: implementing the cycle check with a slower structure (a plain visited-array BFS/DFS per candidate edge, $O(V+E)$ each) instead of Union-Find, which turns an $O(E \log E)$ algorithm into something closer to $O(E \cdot (V+E))$ in the worst case, since every one of the $E$ edges could require a full traversal to check.
• Kruskal's is a better fit than Prim's when the edge list is already available and sorting is cheap relative to the graph's density (sparse graphs); Prim's, which grows a single tree outward using a priority queue keyed on the CHEAPEST edge crossing the current tree's boundary, tends to be preferred on dense graphs where an adjacency-matrix-backed Prim's can run in $O(V^2)$ without ever needing to sort the full edge list.

Direct answer

Implement the two DSU (disjoint set union) primitives, find with path compression and union with union by rank, then answer each connectivity query with two find calls: x and y are connected exactly when find(x) == find(y). Building the structure from k1 edges and then answering k2 queries costs $O((k_1 + k_2) \cdot \alpha(n))$ total, effectively linear in the number of edges plus queries, because each find/union call is amortized near-constant time regardless of how many queries follow.

Structured elaboration

Why process all edges before any query, rather than interleaving. If queries only need to reflect the FINAL state of the graph (all edges applied), building the DSU once from every edge and then answering every query against the completed structure is both simpler and no less efficient than interleaving, since Union-Find has no notion of "time" (there is no way to ask "were x and y connected after only the first 3 edges" without re-deriving that from a prefix of the edge list). If a query needs to know connectivity at a specific POINT in an edge stream (not just at the end), that is a fundamentally different, harder problem (offline dynamic connectivity).

Structure:

1. Initialize parent[i] = i and rank[i] = 0 for all n nodes.
2. For each edge (u, v), call union(u, v).
3. For each query (x, y), call connected(x, y), defined as find(x) == find(y), and collect the boolean result.

Why connected needs no special-casing. Because find always terminates at a canonical root regardless of how the tree got built, comparing two roots correctly answers connectivity even for nodes that were merged transitively through several unrelated-looking edges, and even for a node queried against itself (find(x) == find(x) is trivially true, correctly reporting a node connected to itself).

Worked example

from typing import List, Tuple

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1

    def connected(self, x, y):
        return self.find(x) == self.find(y)

def answer_queries(n: int, edges: List[Tuple[int, int]], queries: List[Tuple[int, int]]) -> List[bool]:
    dsu = DSU(n)
    for u, v in edges:
        dsu.union(u, v)
    return [dsu.connected(x, y) for x, y in queries]

if __name__ == "__main__":
    n = 6
    edges = [(0, 1), (1, 2), (3, 4)]
    queries = [(0, 2), (0, 3), (4, 3), (5, 0)]
    result = answer_queries(n, edges, queries)
    print("n:", n, "edges:", edges)
    print("queries:", queries)
    print("results:", result)

Output:

n: 6 edges: [(0, 1), (1, 2), (3, 4)]
queries: [(0, 2), (0, 3), (4, 3), (5, 0)]
results: [True, False, True, False]

Trace by hand: edges build two components, {0,1,2} and {3,4}, with 5 left isolated. Query (0,2): both in {0,1,2}, True. (0,3): different components, False. (4,3): both in {3,4}, True. (5,0): 5 is a singleton, False. All four match the printed output.

Trade-offs and pitfalls

• This is exactly $O((V + k_1 + k_2) \cdot \alpha(n))$, effectively linear, whereas answering each query independently with a fresh BFS/DFS from x toward y would cost $O(k_2 \cdot (V+E))$, since each query would redo a full traversal. Union-Find's advantage here is specifically that it decouples the cost of BUILDING connectivity information from the cost of ANSWERING a query about it: build once, query many times cheaply.
• Common mistake: rebuilding the DSU per query, which defeats the entire point of the structure and degrades performance to the naive per-query traversal cost.
• Common mistake: forgetting that queries against a node index outside [0, n) will raise an IndexError with an array-backed DSU; production code accepting untrusted query input should validate node indices before calling find.
• If queries must reflect an intermediate state of the edge stream (not just the final state), this design is wrong; it silently gives an answer as though all edges are already applied, which is correct only when every query is meant to run against the fully-built graph, as this question specifies.

Direct answer

Dijkstra's algorithm computes shortest distances from a source in a weighted graph with non-negative edge weights by always finalizing the currently-cheapest-known unvisited node next: a min-priority queue keyed on tentative distance guarantees that whatever node is popped has no remaining unexplored node that could offer it a cheaper route, since every other candidate's tentative distance is at least as large. Alongside distances, recording each node's parent (the node that most recently produced its current best distance) lets any shortest path be reconstructed after the fact by walking parent pointers backward from the target to the source.

Structured elaboration

The implementation keeps two parallel maps, dist and parent, both indexed by node. The priority queue holds (distance, node) pairs; a "stale" queue entry (one whose distance no longer matches dist[node], because a cheaper route was found after it was pushed) is simply skipped rather than removed from the heap, which is cheaper than supporting priority-decrease directly.

Worked example

import heapq
from typing import Dict, List, Tuple, Optional

def dijkstra(graph: Dict[int, List[Tuple[int, float]]], source: int) -> Tuple[Dict[int, float], Dict[int, Optional[int]]]:
    # Dijkstra's algorithm with a binary-heap priority queue. Returns
    # (distances, parents): distances[v] is the shortest distance from
    # source to v (inf if unreachable), parents[v] is the node before v on
    # that shortest path (None for the source or an unreached node).
    dist: Dict[int, float] = {u: float("inf") for u in graph}
    parent: Dict[int, Optional[int]] = {u: None for u in graph}
    dist[source] = 0
    pq: List[Tuple[float, int]] = [(0, source)]

    while pq:
        du, u = heapq.heappop(pq)
        if du > dist[u]:
            continue  # a stale, already-improved-upon queue entry
        for v, w in graph.get(u, []):
            if w < 0:
                raise ValueError(f"Dijkstra requires non-negative weights, got {w} on edge ({u},{v})")
            nd = du + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                parent[v] = u
                heapq.heappush(pq, (nd, v))

    return dist, parent

def reconstruct_path(parent: Dict[int, Optional[int]], source: int, target: int) -> List[int]:
    if target not in parent or (target != source and parent[target] is None):
        return []
    path = []
    node = target
    while node is not None:
        path.append(node)
        node = parent[node]
    path.reverse()
    return path if path[0] == source else []

if __name__ == "__main__":
    graph = {
        0: [(1, 4.0), (2, 1.0)],
        1: [(3, 1.0)],
        2: [(1, 2.0), (3, 5.0)],
        3: [],
        4: [(0, 1.0)],  # unreachable from 0
    }
    dist, parent = dijkstra(graph, 0)
    print("Distances from 0:", dist)
    print("Parents:", parent)
    print("Path 0 -> 3:", reconstruct_path(parent, 0, 3))
    print("Path 0 -> 4 (unreachable):", reconstruct_path(parent, 0, 4))
    print("Cheapest route to 3 goes through 2, not the direct 0->1 edge:", dist[3] == 4.0)

    def all_simple_paths(graph, u, target, path, visited, out):
        if u == target:
            out.append(list(path))
            return
        for v, w in graph.get(u, []):
            if v not in visited:
                visited.add(v)
                path.append((v, w))
                all_simple_paths(graph, v, target, path, visited, out)
                path.pop()
                visited.discard(v)

    out = []
    all_simple_paths(graph, 0, 3, [], {0}, out)
    costs = [sum(w for _, w in p) for p in out]
    print("All simple-path costs 0->3:", costs, "min:", min(costs))
    print("Brute-force minimum matches Dijkstra:", min(costs) == dist[3])

Output (actually executed with python3):

Distances from 0: {0: 0, 1: 3.0, 2: 1.0, 3: 4.0, 4: inf}
Parents: {0: None, 1: 2, 2: 0, 3: 1, 4: None}
Path 0 -> 3: [0, 2, 1, 3]
Path 0 -> 4 (unreachable): []
Cheapest route to 3 goes through 2, not the direct 0->1 edge: True
All simple-path costs 0->3: [5.0, 4.0, 6.0] min: 4.0
Brute-force minimum matches Dijkstra: True

The brute-force helper enumerates every simple path from 0 to 3 by recursive DFS and sums each one's edge weights independently of the main algorithm; its minimum (4.0) matches Dijkstra's dist[3], confirming the priority-queue-driven algorithm found the true cheapest route. Two competing routes reach node 1: the direct edge 0 -> 1 costs 4, while the indirect 0 -> 2 -> 1 costs $1+2=3$, strictly cheaper. From there, continuing -> 3 (weight 1) gives total costs of $4+1=5$ for the direct-then-onward route versus $3+1=4$ for the indirect-then-onward route, 0 -> 2 -> 1 -> 3. Dijkstra correctly settles on the cheaper 4, which the brute-force scan of all three simple paths (costs 5.0, 4.0, and 6.0) confirms is indeed the global minimum.

Complexity

Time $O((V+E)\log V)$: each node is popped from the heap at most once for its final, correct distance (stale duplicates are skipped in $O(1)$ each after the pop), and each edge triggers at most one heap push, each costing $O(\log V)$. Space $O(V)$ for dist and parent, plus $O(V+E)$ for the adjacency list and up to $O(E)$ entries transiently sitting in the heap.

Edge cases

• Unreachable node: dist[4] stays float("inf") and parent[4] stays None; reconstruct_path correctly returns [] rather than a path containing a phantom predecessor.
• Negative edge weight: raises ValueError immediately rather than silently producing a wrong answer, since Dijkstra's greedy finalize-on-pop step is only valid under the non-negative-weight assumption.
• Source with no outgoing edges, or isolated node: dist[source] = 0 and the loop simply never finds any neighbors to relax; every other unreachable node stays at inf.
• Multiple parallel edges between the same pair with different weights: handled naturally, since each is just another entry in the adjacency list and only the cheapest one will ever survive a relaxation check.

Trade-offs and pitfalls

• Common mistake: supporting priority-decrease by trying to find and mutate an existing heap entry in place. Standard binary heaps do not support efficient arbitrary-element decrease-key; the lazy-deletion approach here (push a new, better entry, and skip stale ones on pop via du > dist[u]) is simpler to implement correctly and has the same asymptotic complexity.
• Common mistake: forgetting to guard the negative-weight case. A silently-wrong Dijkstra run on a graph with even one negative edge can produce a plausible-looking but incorrect distance, since the algorithm's core assumption (once popped, a node's distance is final) is exactly what negative weights violate.
• Language-agnostic shape. The same three data structures (a distance map, a parent map, a min-priority queue) are the entire algorithm regardless of implementation language; a Java version swaps heapq for PriorityQueue, a Go version swaps it for container/heap, but none of the logic above changes. This exact shape shows up repeatedly across languages and engineering contexts, all converging on the same three data structures.
• Plain distance-only variant. Some callers only need dist, never a reconstructed path (for example, a monitoring system computing "distance to nearest healthy replica" for every node, where only the number matters). Dropping the parent map and its bookkeeping is a legitimate simplification in that case, not a correctness compromise, since parent is purely additive machinery on top of the core algorithm.

Direct answer

An articulation point (cut vertex) is a node whose removal increases the number of connected components in the graph; a bridge (cut edge) is an edge whose removal does the same. Both are found in a single depth-first search (DFS) pass using the "low-link" technique: track each node's discovery time and its low-link value (the earliest discovery time reachable from that node's DFS subtree via at most one back edge), and a node/edge is flagged as critical based on how a child's low-link compares to the current node's own discovery time. In a network topology, these are exactly the single points of failure: an articulation point is a device whose failure partitions the network, and a bridge is a link whose failure does the same, both directly actionable signals for where redundancy is most needed.

Structured elaboration

Discovery time and low-link, defined precisely. disc[u] is the order in which DFS first visits u (a simple counter incremented on each new visit). low[u] starts equal to disc[u] and is then lowered to the minimum discovery time reachable from u's subtree by following tree edges down and at most one back edge up past u itself; concretely, low[u] = min(low[u], disc[v]) for every back edge to an already-visited (non-parent) node v, and low[u] = min(low[u], low[v]) after fully exploring each tree-edge child v.

Articulation point condition. For a non-root node u with DFS-tree child v: u is an articulation point if low[v] >= disc[u], meaning v's entire subtree cannot reach back to any ancestor of u (not even u itself, in the strict inequality case) without going back through u, so removing u would strand that subtree. The ROOT of a DFS tree is a special case, handled separately: it is an articulation point exactly when it has more than one child in the DFS tree, since each such child's subtree is only connected to the rest of the tree through the root.

Bridge condition. For a tree edge (u, v) where v is u's child: (u,v) is a bridge if low[v] > disc[u] (strict inequality, unlike the articulation-point condition), meaning v's subtree has NO way back to u or any ancestor of u at all, not even to u itself via some other path, so this specific edge is the only connection.

Why single points of failure matter operationally. In a network topology, both articulation points and bridges directly identify where a SINGLE failure (one device down, or one link down) causes a partition, not merely a slowdown; this is qualitatively different from and more urgent than general redundancy planning, since it names the EXACT minimal set of failures that would split the network, which is the natural prioritization list for where to add redundant links or failover devices first.

Worked example

from typing import Dict, List, Set, Tuple

def find_articulation_points_and_bridges(graph: Dict[int, List[int]]):
    disc, low = {}, {}
    visited = set()
    timer = [0]
    articulation_points: Set[int] = set()
    bridges: List[Tuple[int, int]] = []

    def dfs(u, parent):
        visited.add(u)
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        children = 0
        for v in graph.get(u, []):
            if v == parent:
                continue
            if v in visited:
                low[u] = min(low[u], disc[v])
            else:
                children += 1
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if parent is not None and low[v] >= disc[u]:
                    articulation_points.add(u)
                if low[v] > disc[u]:
                    bridges.append((min(u, v), max(u, v)))
        return children

    for start in graph:
        if start not in visited:
            root_children = dfs(start, None)
            if root_children > 1:
                articulation_points.add(start)

    return sorted(articulation_points), sorted(bridges)

if __name__ == "__main__":
    # Network: two triangles (0-1-2) and (3-4-5) joined by a single bridge edge 2-3,
    # plus a pendant node 6 hanging off node 5.
    graph = {
        0: [1, 2], 1: [0, 2], 2: [0, 1, 3],
        3: [2, 4, 5], 4: [3, 5], 5: [3, 4, 6], 6: [5],
    }
    ap, bridges = find_articulation_points_and_bridges(graph)
    print("articulation points:", ap)
    print("bridges:", bridges)

Output:

articulation points: [2, 3, 5]
bridges: [(2, 3), (5, 6)]

By inspection: removing node 2 disconnects {0,1} from the rest, so it is an articulation point; removing node 3 disconnects {0,1,2} from {4,5,6}; removing node 5 disconnects {6}; the edges (2,3) and (5,6) are each the sole connection to a piece of the graph and so are bridges. All four match the executed output exactly.

Trade-offs and pitfalls

• The articulation-point and bridge CONDITIONS differ by a single inequality (>= versus >), and mixing them up is the single most common implementation bug: using > for the articulation-point check would wrongly exclude u when low[v] == disc[u] (a case where v's subtree CAN reach back exactly to u, but no further, meaning removing u still strands the subtree, so u genuinely is an articulation point despite the border case).
• The root of the DFS tree needs separate handling entirely, since the general non-root formula (low[v] >= disc[u]) does not apply to a node with no parent to be "cut off from"; a root is only critical if it has more than one DFS-tree child, since those children's subtrees are then only interconnected THROUGH the root.
• A node can be an articulation point without any single INCIDENT edge being a bridge, and vice versa is also possible; the two concepts overlap but are not equivalent, and a network engineer reading these results needs both lists, not just one, to fully understand the topology's fragility.
• This algorithm assumes an undirected, simple graph (the if v == parent: continue check specifically handles the back-and-forth of a single tree edge, but does not correctly handle true parallel/multi-edges between the same pair of nodes); a network topology with genuine redundant parallel links between two devices needs the algorithm adjusted to track edge identity, not just endpoint identity, or a duplicate parallel edge would be incorrectly treated as a back edge to the immediate parent and silently ignored.

Direct answer

Offline dynamic connectivity answers connectivity queries over a graph whose edges are added and removed over time, when the ENTIRE sequence of add/remove/query operations is known in advance. The technique: compute each edge's active time interval from its add and remove operations, place the edge into $O(\log T)$ nodes of a segment tree built over the $T$ discrete time steps (the standard interval-to-segment-tree decomposition), then do a single DFS over the segment tree, applying each node's edges via union on entry and undoing them via rollback on exit, answering every query at its own leaf. This requires a Union-Find variant that supports rollback, which means giving up path compression (path compression's parent rewrites are not cheaply undoable) and relying on union by size or rank alone, which still gives $O(\log n)$ per operation, for a total cost of $O((V + E + Q) \log n \log T)$.

Structured elaboration

Step 1: turn add/remove pairs into intervals. For each edge, scan the operation sequence and pair each "add edge (u,v)" with its matching later "remove edge (u,v)" (or the end of the timeline, if never removed), producing a half-open interval $[\text{start}, \text{end})$ during which that edge is present.

Step 2: decompose each interval onto a segment tree over time. A segment tree with $T$ leaves (one per discrete time step) lets any interval $[\text{start}, \text{end})$ be covered by $O(\log T)$ of the tree's internal nodes (the standard segment-tree range-update decomposition). Store the edge itself at each of those $O(\log T)$ nodes rather than applying it directly, since the edge should only be "active" while the DFS is visiting that subtree's time range.

Step 3: DFS the segment tree with a rollback-capable Union-Find. On entering a tree node, union every edge stored there (tracking exactly what each union did, for undo). Recurse into children. At a LEAF (a single time step), the DSU now reflects exactly the edges active at that instant, so answer every query scheduled for that time step directly. On exiting the node (after both children return), rollback every union performed at that node, in reverse order, restoring the DSU to the state it had before this node was entered. This is what makes the technique correct: each edge's effect is scoped to exactly the time range it was decomposed onto, and rollback removes it cleanly once the DFS moves to a sibling subtree where that edge is not active.

Why path compression cannot be used. Path compression permanently rewrites parent pointers for every node along a find path, and there is no cheap way to remember and reverse all of those rewrites for an undo. Union by size (or rank) alone, WITHOUT path compression, still guarantees $O(\log n)$ tree height, and each union call only changes ONE parent pointer (the smaller root gets reattached under the larger), which is trivially undoable by recording that single pointer change (and the size that was overwritten) and reversing it on rollback.

Worked example

class RollbackDSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.history = []

    def find(self, x):
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            self.history.append(None)
            return
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx
        self.history.append((ry, self.size[rx]))
        self.parent[ry] = rx
        self.size[rx] += self.size[ry]

    def rollback(self):
        rec = self.history.pop()
        if rec is None:
            return
        child, old_size_of_root = rec
        root = self.parent[child]
        self.parent[child] = child
        self.size[root] = old_size_of_root

    def connected(self, x, y):
        return self.find(x) == self.find(y)


class OfflineDynamicConnectivity:
    def __init__(self, n_nodes, n_time):
        self.n_time = n_time
        self.tree = [[] for _ in range(4 * max(n_time, 1))]
        self.dsu = RollbackDSU(n_nodes)

    def _add(self, node, node_lo, node_hi, lo, hi, edge):
        if hi <= node_lo or node_hi <= lo:
            return
        if lo <= node_lo and node_hi <= hi:
            self.tree[node].append(edge)
            return
        mid = (node_lo + node_hi) // 2
        self._add(2 * node, node_lo, mid, lo, hi, edge)
        self._add(2 * node + 1, mid, node_hi, lo, hi, edge)

    def add_edge(self, u, v, start, end):
        start, end = max(start, 0), min(end, self.n_time)
        if start < end:
            self._add(1, 0, self.n_time, start, end, (u, v))

    def solve(self, queries):
        answers = {t: [] for t in queries}
        self._dfs(1, 0, self.n_time, queries, answers)
        return answers

    def _dfs(self, node, node_lo, node_hi, queries, answers):
        applied = 0
        for (u, v) in self.tree[node]:
            self.dsu.union(u, v)
            applied += 1
        if node_hi - node_lo == 1:
            t = node_lo
            for (u, v) in queries.get(t, []):
                answers[t].append(self.dsu.connected(u, v))
        else:
            mid = (node_lo + node_hi) // 2
            self._dfs(2 * node, node_lo, mid, queries, answers)
            self._dfs(2 * node + 1, mid, node_hi, queries, answers)
        for _ in range(applied):
            self.dsu.rollback()


def brute_force(n_nodes, edges, n_time, queries):
    # Reference: rebuild a fresh DSU from scratch at every time step.
    answers = {t: [] for t in queries}
    for t in range(n_time):
        dsu = RollbackDSU(n_nodes)
        for (u, v, s, e) in edges:
            if s <= t < e:
                dsu.union(u, v)
        for (u, v) in queries.get(t, []):
            answers[t].append(dsu.connected(u, v))
    return answers


if __name__ == "__main__":
    n_nodes, n_time = 5, 6
    # edge (0,1) present during [0,3); (1,2) present during [2,5); (3,4) present [1,6)
    edges = [(0, 1, 0, 3), (1, 2, 2, 5), (3, 4, 1, 6)]
    queries = {
        0: [(0, 1), (0, 2)], 1: [(0, 2)], 2: [(0, 2), (3, 4)],
        3: [(0, 1), (0, 2)], 4: [(1, 2)], 5: [(1, 2), (3, 4)],
    }

    odc = OfflineDynamicConnectivity(n_nodes, n_time)
    for (u, v, s, e) in edges:
        odc.add_edge(u, v, s, e)
    fast_answers = odc.solve(queries)
    ref_answers = brute_force(n_nodes, edges, n_time, queries)

    print("time  fast            brute")
    for t in range(n_time):
        print(t, fast_answers.get(t, []), ref_answers.get(t, []))
    print("MATCH:", fast_answers == ref_answers)

Output:

time  fast            brute
0 [True, False] [True, False]
1 [False] [False]
2 [True, True] [True, True]
3 [False, False] [False, False]
4 [True] [True]
5 [False, True] [False, True]
MATCH: True

Every time step's answers from the segment-tree-plus-rollback approach exactly match a brute-force reference that rebuilds a fresh DSU from scratch at every single time step, confirming the rollback bookkeeping correctly scopes each edge to only its active interval.

Trade-offs and pitfalls

• This technique is OFFLINE by definition: it needs every add, remove, and query operation known before processing starts, because the interval decomposition in step 1 requires knowing an edge's remove time (or the timeline's end) at the moment it is added. It cannot answer a query against a live, still-growing stream.
• Memory: $O((E + Q) \log T)$ for the segment tree's stored edges across all $O(\log T)$ nodes per edge, plus $O(V)$ for the DSU itself; this is larger than plain Union-Find's $O(V)$ footprint, the price paid for supporting the full add/remove/query timeline in one pass.
• Common mistake: using path compression anyway "for speed," which silently breaks rollback correctness. Path compression's rewrites are not tracked by this rollback scheme; adding it back would require also tracking and reversing every compressed pointer, which erases the whole point of choosing union-by-size-only in the first place.
• Common mistake: forgetting to roll back in the exact reverse order unions were applied at a node, especially when a node has more than one edge; since later unions can depend on the tree shape earlier unions produced, rollback must be last-in-first-out (a stack, as used here), never applied in insertion order or in bulk without respecting that order.