# Data structure - π§βπ« Union Find

Introduction - Whatβs the point of using

`Union Find`

?- Quickly detect whethere there is a
`cycle`

inside a`graph`

. - Check if
`a`

,`b`

are in the same subsets, just check if`find(a) === find(b)`

.

- Quickly detect whethere there is a
Compare

`disjoint set`

to`heap`

, both of them are actually`arraies`

, but logically treated as`tree`

/`graph`

.Optimization:

- Path compression:
- Avoid traversing all the way up to find
`root`

of a given node, we could just set`parent[i] = root`

to flatten the tree. It can be acheived by`while loop`

or`recursion`

.

- Avoid traversing all the way up to find
- Union by rank:
- Imagine this worst case:
- The depth of tree is increasing all the time, and the time complexity of
`find(x)`

will be increased as well. - To avoid this, we use a
`rank[]`

to record the`depth`

of each node. - While doing
`union(x, y)`

, we only`append shorter tree to higher tree`

.

- The depth of tree is increasing all the time, and the time complexity of

- Imagine this worst case:

- Path compression:

1 | class UnionFind { |