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

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


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

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

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

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

(Edit: completely rewrote my answer now that my understanding of the problem is (I hope) clearer.) It sounds like this problem can be reduced to incrementally constructing and improving an approximation of the transitive closure of the graph, as the graph is built and searched. $r(u)$ is, abstractly, the set of all nodes which are reachable from both $u$ ...


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


2

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


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

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

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

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


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

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.


1

You could create an undirected graph which nodes are the clusters from A and B, two clusters being connected if they have a common dot. This graph can be built in time $O(n)$ where $n$ is the number of dots. Then the problem is to find the connected components of this graph. It is a standard problem that has a solution in linear time in terms of the number ...


1

The answer to your first question is that while it takes (roughly) $N$ array accesses to perform one union operation, it takes (roughly) $N^2$ to perform $N$ of them. This is what is meant by the phrase "a sequence of $N$ union commands". Regarding your second question, the first two operations are those that initialize pid and qid, and the body of the loop ...


1

Below are two approaches to your problem. detailed semi-formal proof Since you've provided a minimal context, I will state my assumptions then provide a solution. Moreover, I will use very basic loops rather than the fancy for-each loop since they are easier to prove correctness with ─more accurately, easier for me with my current knowledge. We are ...


1

There's an easy way to find the node that contains a given value. You have two data structures: a union-find data structure (that keeps track of which nodes are in the same equivalence class), and a hashtable (that maps from a value to the node(s) that contain that value). The MakeSet operation adds a new set to the union-find data structure and adds a new ...


1

To union-by-size two trees, you have to find their roots first. Since union-by-size takes logarithmic time (your first bullet), then first must take logarithmic time as well. Here is a more formal argument. Say you want to union-by-size two trees $T_1$ and $T_2$. Assume that their heights are logarithmic in their sizes: $H(T_1)\le \log(n_1)$ and $H(T_2)\...


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