连起来很快，删一条边为什么不能把并查集倒着操作？

"""Keep graph edges and compare rebuilt union-find with BFS after removals."""
import itertools
import json
from collections import deque


class UnionFind:
    def __init__(self, n):
        if type(n) is not int or n < 0:
            raise ValueError("n must be a nonnegative integer")
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, vertex):
        if type(vertex) is not int or not 0 <= vertex < len(self.parent):
            raise ValueError("invalid vertex")
        while vertex != self.parent[vertex]:
            self.parent[vertex] = self.parent[self.parent[vertex]]
            vertex = self.parent[vertex]
        return vertex

    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size[b]
        return True

    def connected(self, a, b):
        return self.find(a) == self.find(b)


def rebuild(n, edges):
    uf = UnionFind(n)
    for a, b in sorted(edges):
        uf.union(a, b)
    return uf


def reachable(n, edges, source, target):
    adjacency = [[] for _ in range(n)]
    for a, b in edges:
        adjacency[a].append(b)
        adjacency[b].append(a)
    queue, seen = deque([source]), {source}
    while queue:
        vertex = queue.popleft()
        if vertex == target:
            return True
        for neighbor in adjacency[vertex]:
            if neighbor not in seen:
                seen.add(neighbor)
                queue.append(neighbor)
    return False


def main():
    # Both input graphs produce the same partition, but deleting (0, 1) differs.
    line = {(0, 1), (1, 2)}
    triangle = line | {(0, 2)}
    line_uf, triangle_uf = rebuild(3, line), rebuild(3, triangle)
    assert line_uf.parent == triangle_uf.parent
    before = list(line_uf.parent)
    line.remove((0, 1))
    triangle.remove((0, 1))
    stale = line_uf.connected(0, 2)
    after_line = rebuild(3, line).connected(0, 2)
    after_triangle = rebuild(3, triangle).connected(0, 2)
    assert (stale, after_line, after_triangle) == (True, False, True)
    checks = 2
    # Independent oracle: all 64 undirected simple graphs on 4 vertices.
    possible_edges = list(itertools.combinations(range(4), 2))
    for mask in range(1 << len(possible_edges)):
        edges = {edge for index, edge in enumerate(possible_edges) if mask & (1 << index)}
        uf = rebuild(4, edges)
        for a, b in itertools.product(range(4), repeat=2):
            assert uf.connected(a, b) == reachable(4, edges, a, b)
            checks += 1
    self_loop = rebuild(2, {(0, 0)})
    assert self_loop.connected(0, 0) and not self_loop.connected(0, 1)
    checks += 1
    assert rebuild(0, set()).parent == []
    checks += 1
    try:
        UnionFind(2).find(-1)
        raise AssertionError("negative vertex accepted")
    except ValueError:
        checks += 1
    print(json.dumps({"checks_passed": checks, "same_parent_before_delete": before,
                      "stale_union_find_says_connected": stale,
                      "line_after_delete_connected": after_line,
                      "triangle_after_delete_connected": after_triangle,
                      "oracle_graphs": 64,
                      "boundary": "simple undirected graphs; rebuilding, not a fully dynamic algorithm"},
                     indent=2, ensure_ascii=False))


if __name__ == "__main__":
    main()