If you are already not familiar with the Union-Find data structure, check out this simple tutorial to understand the data structure. The images help a lot.

Naive Implementation without Optimizations

The worst time complexity for find() or union() is O(n) since it may need to run through the whole chain of parents. So in the worst case, m operations can take O(mn) time.

Optimizations

Union-by-size

Modify union() to make the worst-case time of Θ(log n).

Path compression

find() has an amortized time nearly Θ(1)

With both Union-by-size + Path compression

Worst-case time complexity is Θ(m α(m, n)). for m>n operations, where n is the number of elements in the Union-Find tree.

Now, α(m, n) is constant when amortized over a big number of operations. So this turns the time complexity of m operations is just O(m) so each union or find operation is just O(1) on average!