A disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint(non-overlapping) subsets.

For example: you have three sets which are `S1`, `S2`, `S3`. `S1` has `A`, `B`, `C` three elements. `S2` has `D` and `E` two elements. `S3` has `X`, `Y`, `Z` three elements.

S1 & S2 = None, S2 & S3 = None, S1 & S3 = None.

So these are disjoint set as they have no elements in common, or we can say that their intersection(&) with each other is an empty set.

A union-find algorithm is an algorithm that performs two useful operations on such a data structure:

Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.

Union: Join two subsets into a single subset.

If we use example above, Union(S1, S2) will return a merged set {A, B, C, D, E} named S1, at the same time S2 will be removed.

After that, Find(B) returns S1, Find(D) returns S1, Find(Z) returns S3.

## Cycle Detection

For each edge, make subsets using both the vertices of the edge. If both the vertices are in the same subset, a cycle is found.

pseudo code:

Init:

0 1 2 3 4
-1 -1 -1 -1 -1

Start:

0 1 2 3 4
1 -1 -1 -1 -1
0 1 2 3 4
1 2 -1 -1 -1
0 1 2 3 4
1 2 3 -1 -1
0 1 2 3 4
1 2 3 4 -1

0%