একটি গ্রাফ বাইপার্টাইট কিনা যাচাই#
একটি বাইপার্টাইট গ্রাফ হলো এমন একটি গ্রাফ যার ভার্টেক্সগুলোকে দুটি ডিসজয়েন্ট সেটে ভাগ করা যায় যাতে প্রতিটি এজ দুটি ভিন্ন সেটের দুটি ভার্টেক্সকে কানেক্ট করে (অর্থাৎ একই সেটের ভার্টেক্সগুলোকে কানেক্ট করে এমন কোনো এজ নেই)। এই সেটগুলোকে সাধারণত পার্শ্ব (side) বলা হয়।
তোমাকে একটা অনির্দেশিত গ্রাফ দেওয়া হয়েছে। এটা বাইপার্টাইট কিনা চেক করো, এবং যদি হয়, তার পার্শ্বগুলো আউটপুট করো।
অ্যালগরিদম#
একটা থিওরেম আছে যেটা বলে যে একটা গ্রাফ বাইপার্টাইট হয় যদি এবং কেবল যদি এর সব সাইকেলের দৈর্ঘ্য জোড় হয়। তবে, বাস্তবে ডেফিনিশনের একটা ভিন্ন রূপ ব্যবহার করা বেশি সুবিধাজনক: একটা গ্রাফ বাইপার্টাইট হয় যদি এবং কেবল যদি এটা দুই-রঙে রঙ করা যায়।
চলো একটা ধারাবাহিক BFS ব্যবহার করি, এখনো ভিজিট করা হয়নি এমন প্রতিটা ভার্টেক্স থেকে শুরু করে। প্রতিটা সার্চে, যে ভার্টেক্স থেকে শুরু করি তাকে পার্শ্ব ১-এ রাখি। যতবার আমরা এক পার্শ্বে থাকা একটা ভার্টেক্সের এখনো অভিজিটেড নেইবারে যাই, আমরা তাকে অন্য পার্শ্বে রাখি। যখন আমরা এক পার্শ্বে থাকা একটা ভার্টেক্সের নেইবারে যাওয়ার চেষ্টা করি যেটা আগেই ভিজিট করা হয়েছে, তখন আমরা চেক করি যে এটা অন্য পার্শ্বে আছে কিনা; যদি এটা একই পার্শ্বে থাকে, আমরা সিদ্ধান্তে আসি যে গ্রাফটা বাইপার্টাইট না। একবার আমরা সব ভার্টেক্স ভিজিট করে সফলভাবে তাদের পার্শ্বে রাখলে, আমরা জানি যে গ্রাফটা বাইপার্টাইট এবং আমরা এর বিভাজন তৈরি করেছি।
ইমপ্লিমেন্টেশন#
int n;
vector<vector<int>> adj;
vector<int> side(n, -1);
bool is_bipartite = true;
queue<int> q;
for (int st = 0; st < n; ++st) {
if (side[st] == -1) {
q.push(st);
side[st] = 0;
while (!q.empty()) {
int v = q.front();
q.pop();
for (int u : adj[v]) {
if (side[u] == -1) {
side[u] = side[v] ^ 1;
q.push(u);
} else {
is_bipartite &= side[u] != side[v];
}
}
}
}
}
cout << (is_bipartite ? "YES" : "NO") << endl;