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 এ করে দিচ্ছি ।        

MINMAX ALGORITHM

Game Theory এর প্রবলেমগুলো অনেক মজার হয় । প্রথমত তা পড়তে অনেক মজার ( আপনি কোড করতে পারেন আর নাই পারেন প্রবলেম পড়ে অবশ্যই আপনি মজা পাবেন ) আর দ্বিতীয়ত অধিকাংশ ক্ষেত্রেই কোড খুব একটা বড় হয় না। Game Theory কথা আসলেই আমার কাছে অতি বিখ্যাত ভাইবোন Alice  আর Bob  এর কথা মনে পড়ে। যাদের সারাদিন তেমন কোন পড়াশোনা নাই, নতুন নতুন আজাইরা গেম আবিষ্কার করে খেলা ছাড়া। তাদের খেলার কিছু অলিখিত  Rule  আছে –                                                                                                                                                                         

       ১. তারা সব সময় Optimal খেলবে । Optimal খেলবে মানে হল কেউ কখনই কোন ভুল মুভ করবে না যাতে অপর পক্ষের কোন প্রকার লাভ হইতে পারে ।  মানে খেলার প্রাথমিক অবস্থা দেখেও আপনি বুঝে উঠতে পারেন কে জিততে যাচ্ছে ( initial state দেখে বুঝা গেলেও তারা খেলবে কারণ  খেলা ছাড়া তাদের কোন কাম কাজ নাই )

      ২. সর্বদাই Alice ( মেয়ে তো ) First Move দিবে। আমি এখন পর্যন্ত এমন কোন প্রবলেম পাইলাম না যেইখানে বেচারা Bob কে Alice First Move করতে দিছে।

এখন আসি Minmax বা Minimax Algorithm এ । নাম শুনেই বুঝা যায় একজন Maximum Result  এর চেষ্টা করবে আর অন্যজন অপরজনের এর Maximum Output কে Minimum করার চেস্টা করবে । এই ধরনের প্রবলেমগুলোকে Recursion Relation এ প্রকাশ করা গেলে  খুব সহজেই রেজাল্ট পাওয়া যায়। আমরা এইখানে চেস্টা করব সকল Condition  নিয়ে একটা Game Tree বানানোর ( প্রতি Move এর all possible result ) । একটু কঠিন হচ্ছে , আমরা একটা প্রবলেম নিয়ে আলোচনা করলেই জিনিসটা অনেক সহজ হয়ে যাবে।

Problem :::::::::

আবার সেই বিখ্যাত ভাইবোন Alice আর Bob । তারা কোন Box এ N টা বল রাখল। প্রতি Move কেউ হয় ৩টা নাহয় ৫টা না হয় ১টা বল তুলতে পারবে । মানে হল Valid Move হল ১,৩,৫  যখন কেউ তার টার্মে কোন বল তুলতে পারবে না ও হেরে যাবে অর্থাৎ যে N টা বলের মধ্যে সর্বশেষ বলটা তুলবে ও জিতে যাবে। অপরজন তাকে ফান্টা খাওয়াবে । আর অবশ্যই Alice আপু First Move টা দিবে :P 

Solution ::::::::::::                                                                                                                                        Minimax  বা এমন ধরণের problem করার সময় আমাদের প্রথম ফরজ কাজ হল সকল প্রকার Move নিয়ে Game Tree বানিয়ে ফেলা । ধরি N=6  এখন দেখি কি কি Move Possible  

এখন Alice আর Bob এর খেলার Strategy গুলো খেয়াল করি । Alice তার All possible Move এর মধ্যে থেকে সেই Move টাই করবে যার থেকে Bob এর পক্ষে কোন ভাবেই শেষ বলটা তুলে ফেলা Possible না হয়। তেমনি Bob এর ক্ষেত্রেও একই জিনিস প্রযোজ্য। আচ্ছা এখন আমরা Last Case গুলা খেয়াল করি । যদি কেউ ১,৩ বা ৫ টা বল তার টার্মে পায় তাহলে সে এক Move এই জিতে যাচ্ছে । এর মানে হল ১,৩,৫ হল জিতার state ।   এখন যে যে State থেকে এই ১,৩,৫ এ আসা হল তা অবশ্যই হবে হারার State ।  যেমন ২ অর্থাৎ যার কাছে ২ যাবে ও অবশ্যই হারবে কারণ  ২ থেকে শুধু মাত্র ১ এ যাওয়া যায় যা  বিপক্ষ খেলোয়াড় এর জন্য জিতার State মানে হল তার জন্য এইটা হারার State , এখন আবার যে যে state  থেকে হারার State এ আসা যায় তা অবশ্যই হবে জিতার state । যেমন ৩ , কারণ ৩ থেকে ২তে আসা যায় ( আপনি আবার একবার ও কিন্তু ০ করে দিতে পারেন মানে জিতে যেতে পারেন ,আমরা শুধুমাত্র বুঝার জন্য ধরছি আপনি ২ তে যাবেন ) এবং ২ হচ্ছে একটি হারার state অর্থাৎ ৩ হল জিতার state । এখন N=8 এর জন্য আমরা সকল State গুলো দেখি ।

এখন আমরা Code টা দেখি ।

কোড দেখলে দেখব যে আমরা Valid_Move নামে একটি Function রেখেছি যার কাজ হচ্ছে কোন Move Possible কিনা তা চেক করা। এখন কোন State থেকে যদি এমন কোন Move পাওয়া যায় যাতে বিপক্ষ খেলোয়াড় হেরে যাবে এমন সেই move এ যাব। অর্থাৎ এমন কোন Move পাওয়া মানে আমার জিতে যাওয়া তাই আমি true return করব । নতুবা False ।

এখন সবকিছু বুঝা হয়ে গেলে Uva 10404 প্রবলেম টা করা যেতে পারে ।

Practice Problem : 1

Maximum Bipartite Matching by Kuhn’s Algorithm

                      Maximum Bipartite Matching by Kuhn’s Algorithm

 আপনি হলেন ঘটক পাখি ভাই এর এজেন্ট । আপনার কাছে পাঁচ জন পাত্র ( তুষার, সানিম, অর্ণব, পিয়াস,মাহির ) আর পাঁচ জন পাত্রী আছে ( বিলকিস, কুলসুম, সখিনা,  জরিনা , আম্বিয়া )   বুঝার সুবিধার্থে পাত্রীরা সব পাত্রকেই পছন্দ করে ( কারণ সবাই অনেক বস প্রোগ্রামার আর সবারই মেলা টাকা পয়সা আছে )  কিন্তু  পাত্রদের পার্সোনাল পছন্দ আছে ।

-      তুষার সব পাঁচটা মেয়েকেই পছন্দ  করে।

-      সানিম খুবই ভাল ছেলে ও খালি  জরিনাকে পছন্দ করে

-      অর্ণব ও ভাল ছেলে ও খালি কুলসুমকে পছন্দ করে ।

-      পিয়াস এর আবার সখিনা , আম্বিয়া দুইজনকেই পছন্দ।

-      মাহির সবচেয়ে খুঁতখুঁতে ছেলে ওর এদের কাউকেই পছন্দ না।  

এখন ঘটক পাখি ভাই এর এজেন্ট হিসাবে আপনাকে তাদের এমন ভাবে ম্যাচ করতে হবে যেন ম্যাচিং এর পর বেশির ভাগ মানুষ  খুশী থাকে। ধরেন সানিম খালি জরিনাকে পছন্দ করে এখন আপনি জোর করে ওকে কুলসুম এর সাথে বিয়ে দিয়ে দিতে পারবেন না কারণ তো কুলসুমকে পছন্দ করে না।হয় সানিম জরিনাকে বিয়ে করবে না হলে কাউকেই না। Maximum Matching করানোর জন্য আপনাকে এইভাবে সাজাতে হবে যেন আপনি Maximum বিয়া সাদি দিতে পারেন। 

আচ্ছা Bipartite Graph কি তা একটু বলি । যদি কোন গ্রাফ এর N টা নোড থাকে , এমন এই N টা নোডকে U, V দুইটা Independent   set এ বিভক্ত করা যাবে যাতে U Set  এর প্রত্যেকটা নোড এর সাথে V set  এর কোন না কোন নোড এর সাথে connect থাকবে । এই গ্রাফ এ কোন odd cycle থাকবে না। যেহেতু U,V দুইটা মাত্রই set এ নোড গুলো বিভক্ত odd cycle থাকা possible ও না। আর Independent set U,V এর নিজেদের মধ্যে কোন কানেকশন থাকবে না। মানে U set এর কোন নোড নিজেদের মধ্যে connected থাকবে না।

Solution :::

kuhn’s Algorithm এ আমরা গ্রাফ এর নোড গুলোকে দুইটা পার্ট এ ভাগ করে নেই। এই প্রবলেম এ  Left side ( এইখানে পাত্রদের সেট ) Right side ( পাত্রীদের সেট )  তারপর কোন একটা পার্ট এর থেকে corresponding opposite side এ কানেকশন possible কিনা তা চেক করে bipartite  matching কতটা হচ্ছে তা হিসাব করা হয়। একটু কঠিন হচ্ছে , কোড এর সাথে ব্যাখ্যা করলে সহজ হয়ে যাবে। আমরা পাত্রদের সেটকে (০-৪) নাম্বারিং করি আর পাত্রীদের সেটকে (৫-৯) নাম্বারিং করি।

তাহলে পাত্রদের সেট                                                                                         

                              তুষার == ০ নাম্বার নোড                                               

                              সানিম == ১ নাম্বার নোড

                              অর্ণব == ২ নাম্বার নোড

                              পিয়াস == ৩ নাম্বার নোড

                              মাহির == ৪ নাম্বার নোড

এবং পাত্রীদের সেট                                                                                                                        

                             বিলকিস == ৫ নাম্বার নোড

                              কুলসুম == ৬ নাম্বার নোড

                              সখিনা == ৭ নাম্বার নোড

                              জরিনা == ৮ নাম্বার নোড

                             আম্বিয়া == ৯ নাম্বার নোড

এখন process টা বলে যাই কিভাবে কাজ করে তারপর ব্যাখ্যা করব। যেকোনো এক পার্ট এর নোড থেকে চেক করতে হয় যে ও কোন ম্যাচ পেয়েছে কিনা যদি পেয়ে যায় তাহলে counting  এর জন্য  একটা variable  রাখা হয় যার value   বাড়িয়ে দেওয়া হয় আমরা  একটা ম্যাচ  successfully করতে পেরেছি । আমরা দুইটা সেট কে Left ও Right দুইটা গ্রুপ এ ভাগ করি । ধরে নেই পাত্রদের সেট হল Left .।যেহেতু আমরা নোড গুলোকে নাম্বারিং করে দিয়েছি দুইটা গ্রুপ কে দুইটা array  তে convert করতে পারি .।

 int Left[MAX],Right[MAX];

Left  এ আছে  পাত্রদের ইনডেক্স গুলা , Right  এ আছে পাত্রীদের ইনডেক্সগুলা। প্রথমে সবাইকে -1 দিয়ে initialize করে দেই, মানে কোন ম্যাচ এখনও হয় নাই তাদের মধ্যে । এখন যে কোন এক পার্ট দিয়ে চেক করব। বুঝার সুবিধার্থে Left পার্ট আমরা বেছে নিলাম । Left পার্ট এ আছে পাত্রদের ইনডেক্স । এখন আমাদের একটা loop 0-4 পর্যন্ত চালাইলে হয়ে যায়। 0-4  পর্যন্ত চালানো সময় আমি তাদের চেক করব, কোনভাবে আমরা ম্যাচিং করাতে পারি কিনা, করাতে পারলে আমরা যে count variable এ ম্যাচিং কয়টা হচ্ছে count করছি তা ভ্যালু এক করে বাড়িয়ে দিব। ধরেন প্রথমে তুষার ভাই এর জন্য আমরা ম্যাচ করাব। তুষার ভাই সবাইকে পছন্দ করে। বুঝানোর সুবিধার্থে ধরলাম তুষার ভাই বলল আমি জরিনাকে বিয়ে করব। আমরা তুষার ভাই এর সাথে জরিনার ম্যাচ দিলাম। তারপর আমরা আসলাম সানিম ভাইয়ার ম্যাচ করাতে । সানিম ভাইয়া জরিনা ছাড়া কিছুই বুঝে না, জরিনা তাহার জান প্রাণ । ম্যাচ করাতে গিয়ে দেখি তুষার ভাই জরিনাকে বুক দিয়ে রাখছে আর সানিম ভাইয়ার ও জরিনা ছাড়া অন্য কোন পছন্দ নাই, জরিনা ছাড়া ও বাঁচবে না । আমরা তো মহা বিপদে এখন। কি করব কি করব। অনেক সাহস কইরা গেলাম আবার তুষার ভাই এর কাছে বললাম দেখ ভাই সানিম তো জরিনা ছাড়া বাঁচবে না ও তো  suicide করবে এখন তুমি ভাই জরিনাকে মুক্ত করে দেও। এই কথা শুইনা তো তুষার ভাই  ও কান্নাকাটি করতে লাগল । “ সানিম সুইসাইড করলে তো বাংলাদেশ এত বস প্রোগ্রামার হারাইয়া ফেলবে, না ভাই আমি এই পাপ কাজ করতে পারব না , দিলাম ভাই জরিনাকে মুক্ত করে। তোমরা আমার সাথে কুলসুম এর ম্যাচ করাইয়া দেও। ” আমাদের জানে পানি এলো। করলাম ম্যাচ সানিম ভাইয়ার সাথে জরিনার আর তুষার ভাই এর সাথে কুলসুম এর successful match করাইলাম। এখন পালা অর্ণব ভাইয়ার । অর্ণব এরও একমাত্র পছন্দ কুলসুম। তুষার ভাই কুলসুমকে বুক দিছে শুইনা অর্ণব এর বুক ফাটে তো মুখ ফুটে না অবস্থা । আমরা আবার মহা বিপদে । আবার গেলাম তুষার ভাইয়ের কাছে । সব শুইনা তুষার ভাই এরও মুখ শুকাইয়া গেল। কষ্টে কষ্টে বলল কি আর করা আমারে তাইলে সখিনাকে দেও। আমাদের জানে আবার প্রাণ ( মানে পানি ) এলো। এইবার পিয়াস ভাইয়ার পালা। ও বলে আমারে সখিনা দেও । তুষার ভাইকে দুই দুইবার আমরা কষ্ট দিছে এখন তো আর পারব না, পিয়াস ভাইয়া কে বললাম সখিনাকে তুমি ভুলে যাও ভাই তোমার তো  আম্বিয়াকেও পছন্দ তুমি আম্বিয়া নেও। পিয়াস ভাইয়া ও সব বুঝে রাজি হল। আমরা পাইলাম তুষার ভাই সখিনা, সানিম ভাইয়া জরিনা , অর্ণব ভাইয়া কুলসুম , পিয়াস ভাইয়া আম্বিয়া চারটা ম্যাচ। তারপর পালা মাহির ভাইয়া , ও দেবদাস । কাউকেই ওর পছন্দ না। কি আর করা আমরা চারটা highest matching করাতে পারলাম। এইটাই maximum Bipartite matching .

কোড টা দেখি

কোড এ আমরা দেখতেই পারছি Left , Right নামে দুই গ্রুপ এ আমরা প্রথমে গ্রাফটাকে ভাগ করছি । তারপর কোন পার্ট নিয়ে চেক করছি কয়টা ম্যাচিং possible হচ্ছে । এই কাজটা আমরা dfs or bfs দিয়ে করতে পারি। একটা পার্ট বলি। প্রথমে তুষার ভাই এর জন্য সব Right side free ছিল । তাই প্রথমেই জরিনাকে assign করা গেছে  । এখন সানিম এর সময় এসে দেখি জরিনা এর সাথে আগে থেকেই তুষার ভাই  assigned , তাই আমরা যে ভ্যালু বা যার সাথে ছিল ওকে অন্যকোনটা সাথে ম্যাচ করানো যায় কিনা তা kuhn(Right[v]) দ্বারা কল করে দেখা হচ্ছে। কোড বুঝতে এখন ও প্রবলেম হলে খাতা কলম নিয়ে একটু আকাআকি করলেই হবে।    সব বুঝা হয়ে গেলে লাইট অজি এর ১১৪৯ এখন সল্ভ করা যেতে পারে।

               ************************  HappY Coding ************************

Reference  Link :::: 1.http://apps.topcoder.com/forums/;jsessionid=67A7E36F9522573AFEBF1DADBFBE2313?module=Thread&threadID=684427&start=0&mc=11#1679384

2. http://translate.google.com/translate?hl=en&sl=auto&tl=en&u=http%3A%2F%2Fe-maxx.ru%2Falgo%2F