২ স্যাট

[ বিদ্র :  এই গল্পের  সব চরিত্রই কাল্পনিক বাস্তব জীবনের সাথে মিল নাই ]                                                                                                                      

 [ সংবিধকরণ সতর্কীকরণ :  অতিরিক্ত সিরিয়াসনেস প্রোগ্রামিং লাইফের জন্য ক্ষতিকারক ]  

সময়কাল ২০৩০ ।  আমাদের ম্যাল্টি বিলিওনিয়ার রাফি ভাইয়া অবশেষে বিবাহ এর সিন্ধান্ত নিয়েছেন । টাকা-পয়সা , ক্যারিয়ার অনেক দেখা হইছে এখন ঘরকান্না করা দরকার ।  প্রোগ্রামিং এ তুখড় ভার্সিটি লাইফে রাফি ভাইয়ার এর পিছনে কম রমণীর লাইন ছিল না । কিন্তু ক্যারিয়ার সচেতন  ভাইয়া  কখনই ঘরের পানি ঘোলা করতে দেন নাই ( এমনেই এখন ঢাকা শহরের বেশিরভাগ  ট্যাংকের পানি ঘোলা হইয়া গেছে :( )  ভাইয়া এই প্রোগ্রামটা কিভাবে করব ? ভাইয়া এইটা বুঝতেছি না ? ভাইয়া এইখানে জিলাপির প্যাচ লাগছে ছাড়াইয়া দেন :( এরকম কত নাম না জানা , প্রকাশিত এবং অপ্রকাশিত , হাজার রকমের ইমো যুক্ত কত ফেসবুক ম্যাসেজ আসত তার হিসাব নাই । কিন্তু আমাদের বেরসিক রাফি ভাইয়ার এক রিপ্লাই "www.google.com" :(   প্রগ্রামার না  বুঝে নারীর মনের ইঙ্গিত , আফসোস । কি আর করা সময় , নদীর স্রোত এবং নারি কখনই কারো জন্য অপেক্ষা করে না । ভার্সিটি লাইফের নাম না জানা হাজারও ইনা , বিনা , টিনা এখন বিবাহ করে বাচ্চাকাচ্চা সহ সুখে শান্তিতে আছে । যদিও সেই ২৮ ইঞ্চির পেট এখন সাড়ে ৪৪ ইঞ্চি হইছে কিন্তু রাফি ভাইয়ার চ্যারম এখনও তেমন কমে নাই ;) । বিবাহের মার্কেটের  রাফি ভাইয়ার সিন্ধান্ত লিক  হইতে না হইতেই চারিদিক দিয়ে ভাইয়ার জন্য পাত্রীর লাইন লাইগা গেল । আমরাও পড়লাম  মহাবিপদে , কিন্তু ভাইয়ার এত এত awesome পিচ্চি ভাই থাকতে এইটা কোন প্রবলেম :P আমরা অনেক কষ্টে চার জনের সর্ট লিস্ট করলাম । 

(১) নায়লা নাইম (২) সাফা কবির   (৩) মাহি  (৪) ববি 

ভাইয়া আবার চার জনকেই সমান পছন্দ করেন , কাউকেই কম বেশি না :( আর ভাইয়া অনেক ভাল মানুষ এবং ভাল  মানুষের জন্ম , বিবাহ , মৃত্যু একবারই হয় তাই ভাইয়াও চান না পরিবারে কাউকে কষ্ট  দিতে । ভাইয়ার পাত্রী নিয়ে বাবা , মা , ভাইয়া ( ভাইয়ার ভাইয়া ) , আপুর সবারই নিজের কিছু চাওয়া পাওয়া আছে । ব্যাপারটা কিছুটা এমন                           

বাবা চান মাহি এবং নায়লা নাইম কেউই বউ না হোক।                                                                                                   মা চান সাফা কবির বা  মাহি  হোক।                                                 

ভাইয়া চান নায়লা নাইম হোক কিন্তু ববি না হোক ।

আপু চান ববি এবং  নায়লা নাইম  কেউই না হোক ।                                                                                                                                                                                

ব্যাপারটা কিছুটা এমন সবার একটা করে সিন্ধান্ত রাখা হইলেই তারা খুশী থাকে কিন্তু একটাও যদি কোন না রাখা না হয় তাহলে তারা অনেক কষ্ট পাবেন । এবং ভাইয়াও চান সবাইকে খুশী রাখতে । যদি আমরা সবাইকে খুশী রাখতে চাই তাহলে সবার চাহিদাকে এমন একটা boolean expression এ প্রকাশ করতে পারি                                                                 

( মাহি বউ হবে না || নায়লা নাইম হবে না ) && ( সাফা কবির হবে ||  মাহি হবে  ) && ( নায়লা নাইম হবে || ববি হবে না ) && ( ববি হবে না || নায়লা নাইম ও হবে না )                                                                                                                                                                                                                                       

যদি উপরের expression টার ভ্যালু আমরা ট্রু দেখাতে পারি তাহলে আমরা বলতে পারব যে এমন কোন ব্যাবস্থা আছে যেখানে সবাই খুশী থাকে । এইরকম ভাবে কোন প্রবলেমকে আমরা কোন boolean expression এ প্রকাশ করতে পারলে এই টাইপের প্রবলেমগুলা  ২ সেট আল্গরিথম দিয়ে খুব সহজেই সমাধান করা যায় । এইখানে আমরা এই ২ স্যাট আল্গরিথম এর কাজ এই দেখব । 

২ স্যাট  : 

তত্ত্বীয় সংজ্ঞায় আসি , ২ স্যাট হইল প্রতিটা ভ্যারিয়্যাবলের ( এইখানে কোন এক পাত্রী বউ হবে কি হবে না তাই ভ্যারিয়বল ) একটা ভ্যালু সেট যাতে পুরা এক্সপ্রেশনটা ট্রু হয় । এইখানে কতগুলা ব্যাপার খেয়াল করি , 

১) যদি ফাইনাল সেট এ কোন ভ্যারিয়েবল X = true  হয় তাহলে notX = true ও হবে , ধরি এইখানে  X = মাহি বউ হবে তাহলে notX = মাহি বউ হবে না  । মানে এইখানে যদি ফাইনাল ট্রু এক্সপ্রেশন এ দেখা যায় মাহি বউ হবে = ট্রু তাহলে সেট এ মাহি বউ হবে না ওই ভ্যারিয়বলটাও  = ট্রু  হবে । যদি এমন না হয় তাহলে কখনই এক্সপ্রেশন এর ভ্যালু ট্রু পাওয়া যাবে না । এইটা থেকে আমরা আবার আরো একটা ব্যাপারে নিশ্চিত হইতে পারি । যদি variable থাকে Nটা ( এইখানে পাত্রীর সংখ্যা )  তাহলে  2N সংখ্যক নোড থাকবে এক্সপ্রেশন এ । 

২) আমি প্রতিটা নোডকে যদি একটা directed graph এ represent করতে পারি এবং তাতে যদি SCC ( strongly connected component )  বের করি তাহলে প্রতিটা সেট এর ( এইখানে বাবা , মা , ভাইয়া , আপুর ইচ্ছাগুলা একটা সেট ) এইখানে যেহেতু সবারই একটা না একটা ইচ্ছা পূরণ হইতেও হবে তাহলে আমরা এক্সপ্রেশনটাকে এইভাবেও দেখতে পারি । যেমন বাবার ইচ্ছা হইল "  মাহি এবং নায়লা নাইম কেউই বউ না হোক  ( মানে এর দুইটার একটা অত্যন্ত সত্য হোক ) " এখন একটু ব্যাপারটা খেয়াল করলেই ক্লিয়ার হয়ে যাবে ,              

*******যদি কোন ভাবে মাহি বউ হয়ে যায় তাহলে বাবার ইচ্ছা পূরণ করার জন্য নায়লা নাইম অবশ্যই বউ হইতে পারবে না ( আসলে এইখানে ইলেকশন এর ব্যাপারটা দিলে বুঝতে সুবিধা হইত , বউ তো একজন এই হয় এইটা নিয়া কেউ কনফিউজ থাইকেন না , ২Set all possible true expression এর ভ্যালু দেয় মানে একাধিক বউ হইলেও দেখা যাইতে পারে expression true আছে )                                                                                                                                                                                                                                                                                                                                                                                                ******* যদি কোনভাবে নায়লা নাইম বউ হয়ে যায় তাহলে বাবা চান কখনই মাহি বউ হবে না ।                                                                                                           

ধরে নেই   X = মাহি বউ হবে না , Y = নায়লা নাইম বউ হবে না  । এখন যেহেতু একটা একটা সত্য থাকবেই তাই SCC তে মাহি বউ হবে না ( X )  এবং নায়লা নাইম বউ হবে ( !Y ) একই সেট এর হবে  । আর একটা ব্যাপার SCC তে কখনই X এবং !X node এক color এর হইতে পারে না , যদি হয় তাহলে এক্সপ্রেশন এর ভ্যালু কখনও ট্রু হবে না । এইগুলা গেল তত্ত্বীয় ব্যাপার এখন আমরা কোড দেখতে পারি , আসলে কি করতে হবে এবং কিভাবে কাজ করে । 

কোড :                

   (১) ২ সেট এ আমাদের সবার প্রথমে প্রতিটা পারশন এর জন্য তাদের চাহিদার সেট গুলার varibale কে আমাদের directed graph এর কনভার্ট করতে হবে । 

যেমন এইখানে বাবা চান 

মাহি এবং নায়লা নাইম কেউই বউ না হোক 

এর মানে হইল যদি কোন ভাবে মাহি বউ হয় তাহলে নায়লা নাইম বউ হবে না , আর কোন ভাবে যদি নায়লা নাইম বউ হয় তাহলে অবশ্যই মাহি হবে না । 

মানে সোজা কথা 

মাহি বউ - > নায়লা নাইম বউ না 

নায়লা নাইম বউ -> মাহি বউ না । 

এখন বুঝার সুবিধার জন্য আমরা সবগুলা varibale কে numbering করে ফেলি 

ধরি এইখানে , 

নায়লা নাইম বউ -> ০ নাম্বার  নোড 

নায়লা নাইল বউ না -> ১ নাম্বার নোড 

সাফা কবির বউ -> ২ নাম্বার নোড 

সাফা কবির বউ না -> ৩ নাম্বার নোড 

মাহি বউ -> ৪ নাম্বার নোড 

মাহি বউ না -> ৫ নাম্বার নোড 

ববি বউ -> ৬ নাম্বার নোড 

ববি বউ না -> ৭ নাম্বার নোড 

তাহলে বাবার জন্য এইরকম হবে 

বাবা চান মাহি এবং নায়লা নাইম কেউই বউ না হোক 

মানে এইখানে, 

 ৪ - > ১

০ - > ৫ 

এর মধ্য কানেকশন আছে । 

মা এর জন্য হবে 

মা চান সাফা কবির বা  মাহি  হোক 

মানে এইখানে 

২ -> ৫ 

৪ -> ৩ 

এর মধ্য কানেকশন আছে । 

ভাইয়ার জন্য হবে 

ভাইয়া চান নায়লা নাইম হোক কিন্তু ববি না হোক 

মানে এইখানে 

১ -> ৭ ( নায়লা নাইম না হলে ববি অবশ্যই বউ হবে না ) 

৬ -> ০ ( যদি ববি বউ হয়ে যায় অবশ্যই নায়লা নাইম হবে ) 

আপুর জন্য হবে 

আপু চান ববি এবং  নায়লা নাইম  কেউই না হোক । 

মানে এইখানে 

৬ -> ১ ( ববি হয়ে গেলে নায়লা নাইম হবে না ) 

০ -> ৭ ( নায়লা নাইম হয়ে গেলে ববি হবে না )                                                                                                                                                                                          

(২) এখন আমাদের দ্বিতীয় কাজ হইল SCC বের করা এই গ্রাফ এর ।                                                                                                                                     

উপরোক্ত গ্রাফে যদি এখন আমি topological সর্ট চালাই তাহলে order পাব ( হাতে করে দেখতেই পারি ) ৬ ৪ ৩ ২ ১ ০ ৭ ৬ ৫ এর পর যদি SCC color করি । দেখা যাবে যে সব নোড এইখানে আলাদা আলাদা color হয়েছে ।                                                                                                                                                                     

৬ ->  ১ নাম্বার  কালার                                                                                                                                                                                           

৪ ->  ২                                                                                                                                                                                                     

৩ - > ৩                                                                                                                                                                                                          

২ -> ৪ 

১ -> ৫ 

০ -> ৬ 

৭ -> ৭ 

৫ -> ৮ 

(৩) এখন চেক করার two সেট হবে কিনা  simple একটা for loop চালাইয়া এই চেকটা আমি করতে পারি । 

আমি দেখব যে কোন varibale X এর কালার ১ হলে notX এর কালার কি , যদি কোনটাতে same পাওয়া যায় তাহলে এইখানে two sat possible না । 

(৪) এখন হল প্রিন্ট এর কাজ আমি এখন চেক করব কোন নোড x আমাদের Ans হবে যদি  X কালার > notX এর কালার হয়। মানে এইখানে নায়লা নাইম বউ হবে যদি ( color of nayla Nayim > color of not  Nayla Nayim after SCC ) উপরের কোড এ তাই আমরা দেখব নায়লা নাইম বা সাফা কবির যে কাউকেই রাফি ভাইয়া যদি বিয়ে করেন তাহলে পরিবারের সবাই খুশী থাকে । 

আমি আসলে যা জানি তা লিখার চেস্টা করলাম , আমি খুবই বাজে কোডার অবশ্যই ৯৯% কেউই কিছু বুঝে নাই :P এখন গুগল করে সবাইকে বুঝতে হবে ।  যাই হোক , কোড maxima তে থাকার কারনে দিলাম না ।  

লিঙ্ক : http://e-maxx.ru/algo/2_sat

বুঝা হয়ে গেলে Loj   এর ১২৫১ করা যাবে :)