0
$\begingroup$

The task is to make data structure with the following operations:

query: takes two arguments s and t and returns true if they are in the same set and false otherwise.

union: takes two arguments s and t and creates a union of the two sets that contain s and t such that if s is in S and t is in T it removes S and T and replaces it with the union of S and T.

move: takes two arguments s and t and takes s out of its current set and moves s and only s to the set containing t.

union and move don't do anything if s and t are in the same set.

My question is: how do you make an efficient version of this data structure that is < O(n²)?

$\endgroup$
3
  • 1
    $\begingroup$ If everything but the last line is a third party task, please put in a block quote and tell who originated it and how you came to know it. $\endgroup$
    – greybeard
    Jun 7, 2021 at 20:09
  • $\begingroup$ It's homework. I wouldn't know how $\endgroup$
    – user138448
    Jun 7, 2021 at 20:32
  • $\begingroup$ What's $n$? Is it the number of elements in your universe? Is the goal really that of implementing each operation in $o(n^2)$ time? $\endgroup$
    – Steven
    Jun 9, 2021 at 10:13

1 Answer 1

1
$\begingroup$

You want Union-Find with deletions (Kaplan et al. 2002, and Alstrup et al. 2005). You can do deletion in constant time, but it's non-trivial.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy