与“联合并查找”相反的操作
我们知道对于不相交的集合有“并并查找”。 http://en.wikipedia.org/wiki/Union_find
但是如何进行反向操作呢？考虑一个由 N 个节点与 E 个边连接的集合（实际上是一个图）。 在每一步中，我们都想删除一些边，并检查此删除操作是否会导致另一个不相交集。是否可以像“联合查找”那样快速完成？
PS这不是作业，我们有假期:)
We know there is "Union and find" for disjoint sets.
http://en.wikipedia.org/wiki/Union_find
But how to do reverse operation ? Consider a set with N nodes connected with E edges( which is in fact a graph ).
And at each step we want to delete some edge and check if this delete operation leads to have another disjoint set. Is it possible to do it fastly like in "Union and find"?
P.S this is not homework, we have holiday :)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这称为在线边缘删除问题或在线连接问题。一些算法链接位于维基百科关于图连通性的文章部分 。
This is known as the online edge deletion problem or online connectivity problem. Some links to algorithms are in this section of the Wikipedia article on graph connectivity.
所以你的问题是如何有效地检测桥？这可以在线性时间内完成（另见链接）。
So your question is how to efficiently detect a Bridge? This can be done in linear time (also see the link).
Kruskal算法采用并查，反复添加最小权值的边，不构成循环。 反向删除算法，它似乎可以利用一些复杂的数据结构（参见维基百科）。
Union-find is used in Kruskal algorithm, which repeatedly adds edge of minimum weight which doesn't make a cycle. A reverse idea - removing edges of maximum weight as long as it doesn't disconnect the graph - is used in reverse-delete algorithm, which seemingly can make use of some complicated data structure (see Wikipedia).