Union Find Algorithm

                                                        Union Find Algorithm

নাম থেকে বুঝা যায় Union Find Algorithm কোন disjoint dataset এর  কোন element কোন particular sub set এর অন্তর্ভুক্ত কিনা  তা নির্ণয় করে । যদি practical Life example হিসাবে দেখি সামনেই ২০১৪ বিশ্বকাপ ফুটবল আসতেছে । আমাদের সবাই  কোন না  কোন দলকে সাপোর্ট করব । এইখানে sub set আছে ৩২টা ( ৩২টা টিম অংশগ্রহণ করছে ) এখন আমরা যদি disjoint dataset হই , তাহলে আমাদের মধ্যে union Find Algorithm নিদিষ্ট সংখ্যক ব্যক্তির মধ্যে  কে কোন টিম এ সাপোর্ট করে অর্থাৎ কোন টিম এ কতজন সাপোর্টার আছে তা বের করে দিবে । যদিও একই কাজটা আমরা DFS দিয়েও করতে পারি । তাছাড়াও আমরা Union Find দিয়ে কোন undirected graph এর cycle detect করতে পারি ।

কিভাবে কাজ করে ?

Union Find Algorithm এ আমরা সব গুলো elementকে আলাদা আলাদা component হিসাবে ধরে নেই ।

 

তারপর যদি কোন particular element দ্বয়ের মধ্যে connection থাকে অর্থাৎ তারা একই গ্রুপ এর অন্তর্ভুক্ত হয় তাহলে তাদের একই গ্রুপ এর করে দেই ।

এমন ভাবে

এই ঘটনাকে আমরা এইভাবে compare করতে পারি , রাজায় রাজায় যুদ্ধ হয় , সেই রাজা জয়লাভ করে উনি পরাজিত রাজার সব রাজ্যও জয়লাভ করে । অথবা আমাদের বর্তমান রাজনৈতিক পরিস্থিতিতে অনেক নেতাই নতুন নতুন দল এ যোগদান করে । এক নেতার সাথে অনেক সাঙ্গপাঙ্গ থাকে নেতার যোগদান মানে সাঙ্গপাঙ্গদের ও যোগদান এমন । এখন এই কাজগুলা করা জন্য সচরাচর তিনটা function ব্যবহার করা হয় । আমরা basic code টা দেখি
   
                                           

এইখানে par[] arrayতে প্রাথমিক ভাবে সব গুলো element unique marking value  ( সচরাচর কোন elementকে তার ID দ্বারা মানে কোন গ্রাফ এর বিভিন্ন node থাকলে তাদের সবাইকে তাদের node number দ্বারা mark করা হয় )  এখন এইখানে find_parent() , Make_union() , isUnion() function গুলো কি কাজ করে বলি ।

১। find_parent() এর কাজ হল কোন অবস্থায় কোন element কোন গ্রুপের অন্তর্ভুক্ত তা বের করে দেওয়া ।

২। Make_union() এর কাজ হয় দুইটা different গ্রুপ এর element কে কোন এক গ্রুপ এ convert করা ।

৩। IsUnion() এর কাজ হল কোন দুইটা element একই গ্রুপে অন্তর্ভুক্ত কিনা তা চেক করা ।

এখন আমরা একটা প্রবলেম দেখি এবং তা কিভাবে Union Find দিয়ে সল্ভ করা যায় তা দেখব ।

problem ::::

প্রবলেম হিসাবে আমরা Uva এর 459   ( Graph connectivity ) নেই

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=6&problem=400&mosmsg=Submission+received+with+ID+12977069 যদিও এই প্রবলেম এ input একটু প্রবলেম করে । এইখানে বলা হয়েছে আমাকে একটা গ্রাফ এর highest node দেওয়া হবে এবং তাদের মধ্যে যে সব নোড connected তাদের information দেওয়া হবে আমাকে বলতে হবে আমরা গ্রাফটা কে কয়টা Disjoint set  এ ভাগ করতে পারি ।

Solution Code ::  http://ideone.com/GkWzlG

এইখানে অবশ্যই প্রথমে যত নোড তত ans হবে প্রাথমিক ভাবে । তারপর আমি যতবার Make_Union function() টা use করব আমি ans এর value এক কমিয়ে দিব কারণ আমি দুইটা আলাদা set কে এক set এ করে দিচ্ছি ।