7

Seidel and Sharir proved in 2005 [1] that using path compression with arbitrary linking roughly on $m$ operations has a complexity of roughly $O((m+n)\log(n))$. See [1], Section 3 (Arbitrary Linking): Let $f(m,n)$ denote the runtime of union-find with $m$ operations and $n$ elements. They proved the following: Claim 3.1. For any integer $k>1$ we have $...


5

I edited your question to make it self-contained. The literature on uncertain graphs is really rich for this problem. What you are looking for is "reachability in uncertain graphs", which has been studied extensively in database community [1]. Basically, you have an edge between two vertices $u$ and $v$ with probability $p_{uv} \in (0,1]$. You need to find ...


5

It sounds like you're looking for "decremental connectivity". The fastest result I could find was Wulff-Nilson's "Faster deterministic fully-dynamic graph connectivity", which "supports updates (edge insertions/deletions) in $O(\log^2 n/ \log \log n)$ amortized time and connectivity queries in $O(\log n/ \log \log n)$ worst-case time, where $n$ is the number ...


4

In each node store an additional field named "value". The value of a root $r$ represents $\text{FIND}(r)$ (so the root itself is not necessarily $\text{FIND}(r)$). For $\text{SET_TO_1}(i)$, let $r$ be the root of the tree $i+1$ belongs to, we in addition change the value of the new root to the value of $r$. Now which root becomes the new root does not matter ...


4

Firstly, here is the precise statement of the case 2 in OP's question. A sequence of m MAKE-SET, UNION, and FIND operations, n of which are MAKE-SET operations, can be performed on a disjoint-set forest with union by rank in worst-case time $O(m\log_2 n)$. In fact, it is trivial to see that the MAKE-SET and UNION operations run in $O(1)$ time. So the ...


3

If you combine union by rank or union by size with e.g. path compression the amortized complexity is the same [$O(m\alpha(m,n))$]. But notice that Wikipedia uses union by rank in order to prove the upper bound $O(m\log^*(n))$ because for proof purposes the union by rank algorithm is simpler to handle. On the other hand if you are implementing such a data ...


3

The way it works is that your sets are connected components of the graph. You build such components incrementally, adding one edge at a time. When you add each edge, you ask if the vertices are part of the same component, if so then you have a cycle, if not, then you join the two components (perform a set union). Keep adding edges until you run out of them ...


3

Because then a Union operation would be very slow: when you Union two trees, you would have to reparent all of the nodes in one of the trees.


3

Short answer: indirection. For instance, each object could have a field that contains an index into the id array. Or, you could use pointers. Standard union-find data structures often use pointers instead of integers/indices/arrays. Thus, each object has a pointer to another object in the same equivalence class. See, e.g., https://en.wikipedia.org/wiki/...


3

Let the answer be a complete graph $G = (V,E)$ with $|V| = n$ and a weight function $W : E \to \mathbb{R}$ Let the vertices be denoted by $1,2,\dots n$ and edges between $i$ and $j$ as $(i,j)$. Now define the weights of all the edges as follows: $$W(i,j) = j-1, \forall \ 1 \le i < j$$ (Assuming you break ties for the edges on the basis of the value of ...


3

I don't know what the amortized running time is, but I can cite one possible reason why in some situations you might want to use both rather than just path compression: the worst-case running time per operation is $\Theta(n)$ if you use just path compression, which is much larger than if you use both union by rank and path compression. Consider a sequence ...


3

For each equivalence class $X$ of $R_1$, find the representatives of all elements of $X$ in $R_2$. This tells you how the elements of $X$ split in $R_1 \cap R_2$. (You might need to use some efficient data structures or algorithms beyond union-find.) Repeat for all other equivalence classes. Total running time is $\tilde{O}(n)$.


2

I assume that the height of a node $\small x$, denoted as $\small h(x)$, is recursively defined as: $$ \small h(x) = \begin{cases} 0 & \text{ if $x$ is a leaf} \\ 1+\max\{h(y) \mid y\text{ is child of } x\} & \text{ otherwise } \end{cases} $$ Let the value of the potential function before calling $\small \texttt{Find}(x)$ be $\small \Phi$ and the ...


2

Figured this out. Since uf.Union is an inverse ackermann it grows so slowly that it could be considered constant. thus the second loop would run O(clgn) giving and expected output of O(n + clg n))


2

This is an alternative implementation that does not use union-find. When compared to your implementation (with the tweak by xskxzr), my implementation has both advantages and disadvantages. Advantages: It has a real $O(1)$ GET_VALUE instead of an amortized nearly-$O(1)$ one It could implement SET_TO_0, or even SET_TO(i, n) for any n (with FIND still ...


2

You don't say which union-find implementation you are talking about. On the abstract level, all is good; in the first quote, the authors already state that integers represent arbitrary objects! In OOP-speak, as long as your objects have unique integer identifiers, you can immediately apply the material. In many languages, object identity will suffice. In ...


2

In a union-find data structure, each item is either a root or points at a parent. For us, units will be items, and each pointer to a parent will be annotated with the appropriate conversion. You can maintain this annotation while running the usual operations on the union-find data structure. Using this annotation union-find data structure, you can implement ...


2

Imagine merging the larger tree into the smaller one. By doing this, you are guarantying that the new tree will have depth one more than the larger tree's depth. But, if you were to merge the smaller tree into the larger one - the increase in depth would occur only in the branches of the small tree, and since it is small it wont impact the depth (unless the ...


2

Union find is a data structure (not an algorithm!) that maintains a collection of disjoint sets $\mathcal{S} = \{ S_1, S_2, \dots \}$ under union operations (i.e., replace two sets with their union) and find operations (given an element $x$, report the set $S_i$ containing $x$). Hopefully it is already clear to you that if, at any point in time, two distinct ...


2

The problem that you stated is known as the Graph Reachability Query problem. You may want to check this paper: An Efficient Algorithm for Answering Graph Reachability Queries, and the references therein. The paper discusses the previously known results as well as optimizes both on the space complexity and the query complexity. The algorithm takes $O(n^2 + ...


1

Yes, you are right. The intervals are of the form (left endpoint, right endpoint). First, consider the following statement: The intervals are indexed in order of increasing right endpoint It means that given a set of intervals $I_{1}, \dotsc, I_{n}$, the $(\textrm{right endpoint of }I_{i})$ $\leq$ $(\textrm{right endpoint of }I_{j})$ for any $i \leq j$ and ...


1

Best analysis I've seen is by Seidel and Sharir "Top-Down Analysis of Path Compression" (SIAM J. Computing 34:3, 515-525 (2005). Still heavy going... Easier to digest is Ericson's chapter in his "Algorithms".


1

Yes, you are correct! You have identified a typo in that book, Algorithms, the fourth edition by Robert Sedgewick and Kevin Wayne. Please check the errata for the first printing (March 2011) of the fourth edition. p. 226 Printed: in the worst case, it needs 2 N + 1 array accesses Fixed: in the worst case, it needs 2 N - 1 array accesses Reported by ...


1

Check out the analysis of path compression in Union-Find by Seidel and Sharir "Top-Down Analysis of Path Compression", SIAM Journal of Computing 34:3 (2005), pp 515-525. Somewhat heavy going, the result you cite is a step on the way to the best-possible bound by their method.


1

The problem is that you want to do a graph traversal every check : that is way too often. Do a graph traversal to find the connected component of each vertex (e.g. give them a number). This takes $O(m+n)$ time. Store these numbers in an array indexed by the vertices, let's call it $A$. Then check if two vertices $i$ and $j$ are in the same connected ...


1

The time complexity for both versions is exactly the same. It is linear in terms of the distance between $p$ and the $root$. Space complexity is a little different. It's easy to see that the iterative version will use constant space. The recursive function will use linear space on paper (each recursive call must store some information about the current ...


1

This is just a note for myself in the future, in case anyone else out their ends up getting stumped by this problem. This answer expands off of @Apass.Jack's answer. To prove that each level has a binomial coefficient, we use induction. The base case of $n=1$ is ${1 \choose 0}$ is 1. $n$ represents the height of the nodes while the $0$ is just an arbitrary ...


1

We will use without a proof the following claim that appears in the "Weighted quick-union analysis" of section "1.5 CASE STUDY: UNION-FIND" of the book. Claim of (strong) worst case: the worst case for weighted quick-union happens when the sizes of the trees to be merged by union() are always equal (and a power of 2). Define tree $W_n$ recursively. $W_0$ ...


1

Unfortunately, that's not possible with the standard data structure for union-find (namely, with the union by rank method). The data structure has invariants that in some cases require making $y$ be the root (namely, when $x$'s rank is smaller than $y$'s rank, you are required to make $y$ the root). If you force $x$ to be the root in such a situation, then ...


1

What they mean is: find data structures and algorithms to implement the MAKE-SET, DISJOINT-UNION, and REPORT operations. That's all that they mean by "represent the family of sets". The representation is the data structure where the data is stored.


Only top voted, non community-wiki answers of a minimum length are eligible