Nothing special here. It’s just a blog post for summarising my algorithm learning course.
- Part 1 - Union Find
- Part 2 - Quick Find
- Part 3 - Quick Union
- Part 4 - Improved Quick Union
- Part 5 - Related Interview Questions
Quick Find idea is to assign all the items in 1 connected component with 1 same id.
q are connected if they have the same id. Every time we do the
union command, we update those 2
items with the same id (and also all other items in the connected component).
The set is organised as an array, where the values are the id of that connected component. At first,
all the items have the id the same with its index (connected to itself). After each call to
we update the id of those 2 items to one of them
To check whether the 2 items are connected, simply check whether they have the same id or not. For example
truebecause 6 and 7 both have id
falsebecause 0 has the id
1and 9 has the id
||O(1)||Only 1 call to check the id of the item|
||O(n^2)||Have to update id of both items all other items having the same id|
union is too slow for
So easy, no need for sample implementation here. Or did I explain too badly?…