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:

1 | for each unvisited edge(u, v) in edge set E |

Init:

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

-1 | -1 | -1 | -1 | -1 |

Start:

1 | Find(0) = 0, Find(1) = 1 |

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

1 | -1 | -1 | -1 | -1 |

1 | Find(0) = 1, Find(2) = 2 |

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

1 | 2 | -1 | -1 | -1 |

1 | Find(2) = 2, Find(3) = 3 |

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

1 | 2 | 3 | -1 | -1 |

1 | Find(3) = 3, Find(4) = 4 |

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

1 | 2 | 3 | 4 | -1 |

1 | Find(2) = 4, Find(4) = 4 |

## Implementation

1 | class DUS: |