CODEWITHSUNDEEP
algorithmfindunion
Krzysztof Lewko
Krzysztof Lewko

Reputation: 1002

reverse operation to "Union and find"

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 :)

Upvotes: 15

Views: 8876

Answers (3)

sdcvvc
sdcvvc

Reputation: 25654

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).

Upvotes: 1

dcn
dcn

Reputation: 4469

So your question is how to efficiently detect a Bridge? This can be done in linear time (also see the link).

Upvotes: 1

Rafał Dowgird
Rafał Dowgird

Reputation: 45171

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.

Upvotes: 8

Related Questions