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(n2)?
-
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– greybeard2021年06月07日 20:09:24 +00:00Commented Jun 7, 2021 at 20:09
-
$\begingroup$ It's homework. I wouldn't know how $\endgroup$user138448– user1384482021年06月07日 20:32:47 +00:00Commented 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– Steven2021年06月09日 10:13:19 +00:00Commented Jun 9, 2021 at 10:13
1 Answer 1
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.