Bipartite Graph Checking

গ্রাফ থিওরি শিখতে গেলেই অনেক আমাদের ধরনের গ্রাফের সাথে পরিচয় হয়ে উঠে, এর মধ্যে বাইপারটাইট গ্রাফ অন্যতম।

এইখানে আমারা গ্রাফের সব নোড গুলাকে দুইটা সেটে বিভক্ত করে ফেলি। এমনভাবে বিভক্ত করি যেনো একই সেটের নোডের মধ্যে কোনো Edge/Vertices না থাকে অর্থাৎ একটা সেটের নোড শুধুমাত্র অন্য আরেকটা সেটের নোডের সাথে কানেক্টেড থাকে।

পাশের চিত্রে খুব সুন্দরভাবে একটা বাইপারটাইট গ্রাফকে দেখানো হইছে। দুইটা সেট U and V তে ভাগ করা হইছে, এবং একই সেটের নোডের মধ্যে কোনো কানেক্টিভিটি নাই।

কোডিং এর ক্ষেত্রেও জিনিস টা সেইম ভাবে চিন্তা করা যায় । আমরা দুইটা সেইটে বিভক্ত না করে, দুইটা কালার দিয়ে রিপ্রেজেন্ট করবো 0 and 1.

DFS মাধ্যমে খুব সহজেই বাইপারটাইট চেইক করা যায়। একটা Visited Array এবং একটা Color Array র মাধ্যমে পুরো প্রসেস টা শেষ হবে। আমরা Boolean Types এর DFS ব্যবহার করবো 

প্রথমে আমরা কালার ১ দিয়ে প্রথম নোড এর DFS চালাবো, এই নোড কে ভিসিটেড এবং কালার এরেতে আপডেট করার পরে, এর এডজেসেন্সি লিস্টে গিয়ে দুইটা জিনিস চেইক করবো 

১। ঐ নোডের চাইল্ডগুলাকে ডিফ্রেন্ট কালার দিয়ে DFS চালালাইলে True/False কি রিটার্ন করে
২। ঐ নোড এবং চাইল্ড সেইম কালার কিনা, সেইম হইলে False

পরিশেষে DFS  True রিটার্ন করবে, কারন এর আগে আমাদের দুইটা কেইস চেইক করার পরেও বাইপারটাইট পাইনাই।

Easy Implementation

Related Problems:
Graph Without Long Directed Paths
BUGLIFE - A Bug’s Life