সবাইকে আবার স্বাগতম স্বশিক্ষার আরেকটি নতুন পর্বে । আমাদের স্বশিক্ষার অনেকগুলো বিভাগের মধ্যে একটি বিভাগ হচ্ছে বিভিন্ন অনলাইন জাজ এ দেয়া প্রবলেম গুলো নিয়ে আলোচনা করা । এই বিভাগে আমরা মূলত আলোচনা করে থাকি কীভাবে আমরা একটা প্রবলেম সমাধানে আমাদের আইডিয়াকে সাজাতে পারি আর সেই হিসেবে সমস্যা সমাধানে অ্যাপ্রোচ করতে পারি ।
আজকে আমরা কথা বলব, একটি অতি সুপরিচিত প্রবলেম নিয়ে । এটি হচ্ছে Uva – 10004, Bicoloring . এটি মূলত একটি DFS অথবা BFS অথবা যে কোন গ্রাফ ট্রাভার্সিং প্রবলেম । এখানে বলা হয়েছে ,
আমাদের একটি গ্রাফ দেয়া থাকবে । আমাদের কাজ হবে সেই গ্রাফের প্রত্যেকটা নোড কালার করা / রং করা আর এমনভাবে রং করা যাতে অ্যাাডজেসেন্ট কোন ২টা নোড এ একই কালার না থাকে । আর যদি আমরা দেখাতে পারি যে গ্রাফটি রং করতে “সর্বোচ্চ” ২টি রং লাগে তাহলে এটি “Bicolorable” অথবা করতে না পারলে “Not Bicolourable” প্রিন্ট করতে হবে ।
Algorithm:
আমরা এখানে প্রবলেমটি কিভাবে DFS দিয়ে করব তা বলছি । কিন্তু এটি BFS অথবা যেকোন গ্রাফ ট্রাভার্সিং মেথডে করা যাবে ।
আমাদের প্রথম কাজ হবে, ডিফএস অ্যাাপ্লাই করে কীভাবে আমরা গ্রাফটি কে ট্রাভার্স করছি সেটা বের করা । আর যখন আমরা পথটা বের করব তখনই আমরা নোডগুলোকে রং করতে থাকব । আমরা জানি আমাদের টার্গেট পুরো গ্রাফটাকে ২টি রং দিয়ে ট্রাভার্স করা । তাহলে আমরা রং করার সময় ২টি রং ই ব্যবহার করব । আর এভাবে রং করব , “যদি আমরা P নোডটি থেকে Q নোড এ আসি , মানে এদের মধ্যে একটি সরাসরি এজ(Edge) আছে, আমরা তাহলে অবশ্যই P তে যেই রংটি আছে Q তে সেই রংটি বাদ দিয়ে অন্য আরেকটি রং দেব ” । এভাবে আমরা পুরো গ্রাফটিকে কালার করব।
এরপর রং করা হয়ে গেলে, আমরা চেক করব, একটা নোড যাদের সাথে কানেক্টেড তাদের কালার আর তার কালার ডিফরেন্ট কিনা । যদি না হয় তাহলে গ্রাফটি Non Biocolorable আর যদি প্রত্যেকটা নোড এর ক্ষেত্রে দেখি, এভাবে যাদের মধ্যে সরাসরি edge আছে তাদের কালার ভিন্ন তাহলে গ্রাফটি Bicolorable .
এটা হচ্ছে একদম সাধারণ চিন্তা । আমরা চাইলে আমাদের সমাধানটিকে আরো এফিসিয়েন্ট করতে পারি । আমরা যদি একটু লক্ষ করি, তাহলে দেখব আমরা যখন রং করছি ইচ্ছা করলে তো ওইসময় আমরা বুঝতে পারি যে এটাতে রং করার সময় কন্ট্রাডিক্ট করছে কিনা, যে নরমালি রং করার সময় আমরা এমন একটা ভার্টেক্স পেলাম যেটাতে ইতোমধ্যে রং করা আছে আর এর পেরেন্ট বা সোর্স ভার্টেক্সটিতে ও একই রং করা । তাহলে আমরা বলতে পারি , যে ভার্টেক্সটিতে আগে থেকেই রং করা ছিল সেটি নিশ্চয়ই ঐ সময় যাতে কন্ট্রাডিক্ট না করে ঐটা মাথায় রেখে রং করা হয়েছিল । আর আমাদের এখন আবার যেহেতু ওইরংটি থাকাতে কন্ট্রাডিক্ট করছে তাহলে অবশ্যই এটি বাইকালারেবল না ।
Code :
আমরা আগে নিজেরা ট্রাই করব না হলে আমরা নিচের কোডটি থেকে কিছুটা সাহায্য পেতে পারি ।
#include <bits/stdc++.h>
using namespace std;
vector <int> graph[250];
int color[250];
int dfs_color_selection(int node)
{
int visit[250] = {0},variable,i,cnt = 0,contradiction = 0;
stack <int> use;
variable = 0;
use.push(variable);
cnt++;
color[variable] = 1;
visit[variable] = 1;
while(1)
{
if(use.empty() == 1)
{
break;
}
variable = use.top();
if(graph[variable].size() == 0)
{
use.pop();
continue;
}
for(i = 0; i < graph[variable].size(); i++)
{
int got = graph[variable][i];
if(visit[got] == 0)
{
visit[got] = 1;
use.push(got);
cnt++;
if(color[variable] == 1) {
color[got] = 2;
}
else {
color[got] = 1;
}
break;
}
if(visit[i] == 1 && i < graph[variable].size() - 1) {
if(color[got] == color[variable]) {
contradiction = 1;
break;
}
}
if(visit[got] == 1 && i == graph[variable].size() - 1)
{
if(color[got] == color[variable]) {
contradiction = 1;
break;
}
use.pop();
}
}
if(contradiction == 1) {
break;
}
}
return contradiction;
}
int main(void)
{
int node,edge,i,a,b;
while(scanf("%d",&node) == 1)
{
if(node == 0)
{
break;
}
scanf("%d",&edge);
for(i = 1; i <= edge; i++)
{
scanf("%d %d",&a,&b);
graph[a].push_back(b);
graph[b].push_back(a);
}
int found = dfs_color_selection(node);
if(found == 1)
{
printf("NOT BICOLORABLE.\n");
}
else
{
printf("BICOLORABLE.\n");
}
for( i = 0; i < node; i++)
{
graph[i].clear();
}
}
return 0;
}