Union-Find (Disjoint Sets)

কোন 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 করে।

Run করে দেখুন

অনুমোদিত: union A B এবং find A (item গুলোর নম্বর 0 থেকে শুরু)। সর্বোচ্চ 15টি operation।

নিজে চেষ্টা করুন

সাধারণ ভুল

Complexity, সহজ ভাষায়: union by size আর path compression থাকলে প্রতিটি operation প্রায় constant সময়ে হয় (O(α(n)), যেখানে α এত ধীরে বাড়ে যে আপনার দেখা যেকোনো input-এর জন্য এটা 5-এর নিচে)। Memory লাগে দুটি ছোট array।