0
$\begingroup$

I'm trying to learn about DSU, and I came across a point stating if two vertices belong to the same sub-set, then a cycle exists. In terms of implementation of DSU, I'm unable to make sense of this. Could you share a proof or explain this?

$\endgroup$
  • 1
    $\begingroup$ What is DSU? Could you please show the original source that states this assertion? $\endgroup$ – xskxzr Mar 20 at 12:14
  • 1
    $\begingroup$ DSU stands for Disjoint Set Union. The term "disjoint-set" or "union-find" is preferable much more. $\endgroup$ – Apass.Jack Mar 20 at 16:09
3
$\begingroup$

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 or found a cycle.

If we look at the definition of connected component, it implies that for each two vertices $u$ and $v$ in the same component, there's a path connecting them.

The algorithm works as follows: you start adding a Singleton set for each vertex to your dsu. These are your first components. Then add the first edge, obviously, the two vertices will be on separate sets (components), and you just found an edge connecting them, so that means they belong to the same component. So you join the two sets (components) into a single one, as your edge is the path connecting them.

You keep going, everytime you find an edge connecting two vertices in different components, you can join the components, as that edge will be a bridge connecting them: if the vertices are $u$ and $v$, and you have $w$ in $u$'s component, you can assert that there's a path from $w$ to $v$ passing through your current edge. Is easy to see now that all vertices in both components are now connecting. So join the two sets (components) in one.

Finally, when you process an edge which vertices $u, v$ are on the same component, you just found a cycle: since both are on the same component, you know there's a path between them, and your new edge happens to close the cycle.

DSU is typically used for implementing Kruskal's algorithm, and uses the same properties. You can do a quick Google search for Kruskal with DSU, for examples.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.