Union-Find (Disjoint Set Union) উপাদানগুলিকে disjoint sets-এ বিভাজন ট্র্যাক করে এবং দুটি near-O(1) অপারেশন সমর্থন করে: find (x কোন সেটে আছে?) এবং union (দুটি সেট মার্জ করুন)। এটি connectivity queries-এ উৎকর্ষ লাভ করে।
The idea
প্রতিটি সেট একটি প্রতিনিধিত্বকারী রুটের সাথে একটি গাছ। এবং সহ, অপারেশনগুলি প্রায় ধ্রুবক সময়ে চলে (inverse Ackermann, α(n))।
