We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [union-find]

Questions about the abstract data structure Union-Find (also called disjoint-set) and its realizations.

Filter by
Sorted by
Tagged with
11
votes
1answer
4k views

Directed union-find

Consider a directed graph $G$ on which one can dynamically add edges and make some specific queries. Example: disjoint-set forest Consider the following set of queries: ...
6
votes
2answers
759 views

Split-Find: maintaining dynamic graph connectivity information, under edge deletion

Is there a data structure to keep track of the connected components of a dynamic graph, when the graph might by changing by deleting edges of the graph? Let $G$ be an undirected graph. I have two ...