Quick Find was very slow with quadratic operations. Quick Union is a lazy union-find algorithm to unite sets and to see if an element is connected to another. We use array to initialize elements to indices itself. Later, we update the elements to point to it's parent. This way we create trees out of elements.
Array accesses:
initialize - N
union(p,q) - N+ including the cost of root calculations
connected(p,q) -N
The trees can get quite tall, making the connected operation quite slow.
Following is the program:
Array accesses:
initialize - N
union(p,q) - N+ including the cost of root calculations
connected(p,q) -N
The trees can get quite tall, making the connected operation quite slow.
Following is the program:
No comments:
Post a Comment