O(1) Make, Find, Union in Disjoint Sets Data Structure
Today, I had discussion with someone about Kruskal Minimum Spanning Tree algorithm because of page 13 of this slide. The author of the presentation said that if we implement disjoint sets using (doubly) linked list, the performance for Make and Find will be O(1) and O(1) respectively. The time for operation Union(u,v) is min(nu,nv), wh...