মডিউল ১০_০ঃ ইনট্রডাকশন

কি অবস্থা সবার? দেখতে দেখতে আমরা গ্রাফ রিলেটেড বেশ কিছু এলগোরিদম শিখে ফেলেছি। আজকে আমরা নতুন একটি ডেটা স্ট্রাকচার শিখব যেটা মুলত দুইটা এলগোরিদমের সমষ্টি। নামে হচ্ছে Disjoint Set Union| অনেকে একে Union Find এলগোরিদম ও বলে থাকে। তাহলে এখন বোঝার চেষ্টা করি জিনিসটা কি?

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

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