Nothing special here. It’s just a blog post for summarising my algorithm learning course.
The underlying data structure for
Quick Union is similar to
Quick Find. We need an array for all
the items. The values are still the id, but it’s the id of the parent item. The connected component
is organised using a tree structure like this
isConnected(p, q)check whether the 2 items have the same root
union(p, q)set the id of p’s root to the id of q’s root
||O(N)||Worst case, have to traverse through all items|
||O(n)||Only need to update 1 id but including the cost of finding roots|
Quick Union is faster than
Quick Find when performing
isConnected command but still too slow
for large data set.