কোন item কোন group-এ আছে তার হিসাব রাখুন, আর group গুলো দ্রুত merge করুন।
মূল ধারণা (বন্ধুদের group)
কল্পনা করুন একটি পার্টিতে মানুষ ধীরে ধীরে বন্ধু হচ্ছে। আপনি জানতে চান "Ana আর Raj কি একই friend group-এ?", আর দুই group-এর সদস্যদের দেখা হলে group দুটি merge করতে চান। Union-find দুটোই প্রায় constant সময়ে করে।
প্রতিটি group হলো একটি tree, আর সবার উপরের ব্যক্তি হলো group-এর root (leader)। parent[i] array বলে প্রতিজন কার দিকে point করছে; leader নিজেই নিজের দিকে point করে।
Find(x): parent ধরে উপরে উঠুন যতক্ষণ না root পান। দুজন একই group-এ থাকে যদি তাদের root এক হয়।
Union(a, b): দুজনের root বের করুন; আলাদা হলে ছোট tree-টাকে বড় tree-র root-এর নিচে ঝুলিয়ে দিন (union by size), যাতে tree গুলো ছোট থাকে।
Path compression: Find করতে উপরে উঠার সময় যাদের পার হয়ে এলেন, সবাইকে সরাসরি root-এর দিকে point করিয়ে দিন। পরের Find প্রায় সাথে সাথে হয়ে যায়।
Run করে দেখুন
অনুমোদিত: union A B এবং find A (item গুলোর নম্বর 0 থেকে শুরু)। সর্বোচ্চ 15টি operation।
নিজে চেষ্টা করুন
Default operation গুলো run করুন এবং find 3 খেয়াল করুন: node 3 সরাসরি root-এর দিকে point করে। এটাই path compression।
union 0 1, union 1 2, union 2 3, union 3 4 করুন। tree কি লম্বা chain হয়ে যায়? না হলে কেন?
union 0 1 দুইবার call করুন। দ্বিতীয়বার কী বলে?
সবকিছু একটি group-এ merge করুন, তারপর যেকোনো item-এ find করুন।
সাধারণ ভুল
root-এর বদলে parent তুলনা করা।parent[a] == parent[b] ভুল, যদি না দুটোই root হয়। সবসময় Find(a) == Find(b) তুলনা করুন।
initialize করতে ভুলে যাওয়া। প্রতিটি item শুরুতে নিজেই নিজের parent হতে হবে: parent[i] = i, size[i] = 1।
root না দেখে merge করা। একই group-এর দুটি item জোড়া লাগালে cycle তৈরি হতে পারে।
ভুল root-এর size update করা। যে root উপরে থাকছে, তার size-এ যোগ করুন।
Complexity, সহজ ভাষায়: union by size আর path compression থাকলে প্রতিটি operation প্রায় constant সময়ে হয় (O(α(n)), যেখানে α এত ধীরে বাড়ে যে আপনার দেখা যেকোনো input-এর জন্য এটা 5-এর নিচে)। Memory লাগে দুটি ছোট array।