All operations are known offline. Reversing time converts unsupported splits into supported union operations.

Do not force the data structure to delete. Change the evaluation order: start at the ending snapshot and replay history backward, where every vanished edge returns.

What the function promises: Operations are delete(u,v) and query(u,v) on an initially undirected simple graph. Each edge is deleted at most once. Return query answers in forward order.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
    def find(self, x):
        while x != self.parent[x]:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x
    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b: return
        if self.size[a] < self.size[b]: a, b = b, a
        self.parent[b] = a; self.size[a] += self.size[b]

def offline_connectivity(n, edges, operations):
    deleted = {tuple(sorted((u,v))) for kind,u,v in operations if kind == "delete"}
    dsu = DSU(n)
    for edge in edges:
        if tuple(sorted(edge)) not in deleted: dsu.union(*edge)
    answers = []
    for kind, u, v in reversed(operations):
        if kind == "query":
            answers.append(dsu.find(u) == dsu.find(v))
        else:
            dsu.union(u, v)
    return list(reversed(answers))

ops = [("query",0,2),("delete",1,2),("query",0,2)]
assert offline_connectivity(3, [(0,1),(1,2)], ops) == [True,False]

Work and storage: Near O((E+Q) α(V)) time and O(V+E+Q) storage.

When to recognize it: Reversing time converts unsupported splits into supported union operations.

Check before applying it: Online answers or repeated add/delete lifetimes require richer interval and rollback techniques.

Assign each edge active time intervals and combine a segment tree over time with rollback union-find.