মডিউল ১০_১ঃ DSU কি?

ম্যাথমেটিকাল ভাবে যদি বলি তাহলে Disjoint Set হচ্ছে এমন দুইটা সেট যাদের মধ্যে পরস্পরের কোনো এলিমেন্ট এর মিল নাই।

যেমনঃ ধরি A = {0,1,2} B = {3,4,5}

তাহলে আমরা যদি A আর B এর কমন এলিমেন্ট গুলো নিয়ে একটা সেট বানায় তাহলে ফাকা সেট পাব। এটিই হচ্ছে DIsjoint Set |

আগের মোডিউলের উদাহরণ টাও যদি আনি তাহলে দেখো

একটা বাস্তব জীবনের উদাহরণ নিয়ে চিন্তা করিঃ

ধরি দুইটা ফ্রেন্ড গ্রুপ আছে এবং একটা গ্রুপের লিডার হলো Rahim আরেকটা গ্রুপের লিডার হলো Rokib| এখন ধরো প্রথম গ্রুপের Sohag আর দ্বিতীয় গ্রুপের Ainul বন্ধু হলো। এতে কি হবে দুই গ্রুপ পরস্পরের বন্ধু হয়ে যাবে। এখন এখানে একটা সমস্যা আছে। একটা সেইম গ্রুপে কখনও দুইজন লিডার থাকতে পারে না। তাহলে যখন দুই গ্রুপ এক হয়ে গেল তখনই যেকোনো একজন লিডার এর তার লিডারশীপ স্যাক্রিফাইজ করতে হবে। তাহলে এই যে পরস্পরের গ্রুপের লিডার খুঁজে বের করা এটা করা হয় Find এলগোরিদমের মাধ্যমে আর দুইজন থেকে যেকোনো একজনকে লিডার সিলেক্ট করছি সেটা করা হয় Union এলগোরিদমের মাধ্যমে। আর এই দুই এলগোরিদমের মাধ্যমে যে ডেটা স্ট্রাকচার দার করানো যায় সেটা হচ্ছে Disjoint Set Union সংক্ষেপে আমরা DSU বলে থাকি।

তাহলে এখন নতুন সেটটি দেখতে হবে অনেকটা এইরকম

তবে এখানে একটা বিষয় হলো দুইটা নোড এর লিডার যদি সেইম হয় তাহলে তাদের মধ্যে Union সম্ভব নই। কেননা তাদের Union হয়ে আছে।