假设我们有一组n个不相交的节点{node1, node2,..., noden}
对于以下三种操作,最快的数据结构和算法是什么:
Union(x,y):在节点x和节点y之间添加无向边,两个节点之间最多只能有一条边。
IsConnected(x,y):如果节点x和节点y直接或间接相连,则返回true,即节点x和节点y在同一个联通分量中。
Un-union(x,y):如果存在,则删除节点x和节点y之间的边。
Disjoint-set是实现前两个操作的完美数据结构,但它不能直接支持第三个操作。有什么替代方案吗?
如果我们模拟这个过程,第一个和第三个操作可以在O(1)时间内实现,但第二个操作需要O(n)时间,因此我想知道是否可能将这三个操作都运行在O(logn)时间或更短的时间内。