মডিউল ১০_২ঃ Union Find কিভাবে কাজ করে?

আমরা বাস্তব জীবনের এক্সাম্পল থেকে DSU সম্পর্কে জেনেছি। এখন দেখব কিভাবে প্রোগ্রামিং এর দিক থেকে এটা নিয়ে চিন্তা করা যায়।

ধরি দুইটা গ্রুপ আছে। একটাতে আছে ১,২,৩ আরেকটাই আছে ৪,৫,৬। আমরা প্যারেন্ট ট্র্যাক রাখার মাধ্যমে লিডার বের করব। একটা প্যারেন্ট এ্যারে মেইনটেইন করব যেটাতে ইনিশিয়ালি সবার প্যারেন্ট থাকবে -১। মানে সবাই সবার প্যারেন্ট।

এটি দিয়ে বোঝায় যে এখনো কারো সাথে কারো রিলেশন তৈরি হয় নি।

ধর এবার আমি ১ আর ২ এর মধ্যে রিলেশন বানাইতে চাচ্ছি। তাহলে দেখব দুইজনের প্যারেন্টকে। যেহেতু এই ক্ষেত্রে দুইজনের প্যারেন্ট -১ তার মানে দুইজনেই লিডার। তাহলে এখানে যেকোনো একজনের লিডারশীপ স্যাক্রিফাইস করতে হবে। ধরে নিলাম ২ তা করবে। তাহলে এখন ২ এর প্যারেন্ট আপডেট হয়ে হবে ১। এই যে লিডার খুঁজে বের করছি এটা হলো find অপারেশন আর নতুন লিডার বানাচ্ছি এটা হলো union অপারেশন।

এখন ধরুন ২ আর ৩ আর মধ্যে রিলেশন বানাইতে চাচ্ছি। এখন ২ এর প্যারেন্ট ১ আর ৩ এর প্যারেন্ট -১। এখানেও আমরা ৩ এর প্যারেন্টকে চেইঞ্জ করে ২ করে দেব।

তাহলে এখন আমরা প্রথম গ্রুপের জন্য প্যারেন্ট এ্যারের দিকে তাকাইলে ৩ এর প্যারেন্ট ২। তারপর ২ এর দিকে তাকাবো দেখবো তার প্যারেন্ট ১। ১ এর প্যারেন্ট -১। তাহলে ১ এই গ্রুপের লিডার।

সেইম ভাবে যদি ২য় গ্রুপে ৪কে লিডার ধরে করি তাহলে প্যারেন্ট এ্যারে হবেঃ

এখন ধর আমরা ২ আর ৫ এর মধ্যে রিলেশন বানাইতে চাই। তাহলে প্রথমে দেখব ২ এর লিডার কে?

সেটা হচ্ছে ১। তারপর দেখব ৫ এর লিডারকে সেটা হচ্ছে ৪। এখন এখানে ১ আর ৪ এর মধ্যে কোনো একজনের লিডারশীপ স্যাক্রিফাইস করতে হবে। ধরলাম ৪ করবে। তাহলে ৪ এর প্যারেন্ট আপডেট হয়ে হবে ১।

এর কারনে এখন দুইগ্রুপের union হয়ে যাবে।