# Using Union find to check whether there is a cycle in a graph

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?

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

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