# 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).
• 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.
• 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.