একটি গ্রাফ বাইপার্টাইট কিনা যাচাই#
একটি বাইপার্টাইট গ্রাফ হলো এমন একটি গ্রাফ যার ভার্টেক্সগুলোকে দুটি ডিসজয়েন্ট সেটে ভাগ করা যায় যাতে প্রতিটি এজ দুটি ভিন্ন সেটের দুটি ভার্টেক্সকে সংযুক্ত করে (অর্থাৎ একই সেটের ভার্টেক্সগুলোকে সংযুক্ত করে এমন কোনো এজ নেই)। এই সেটগুলোকে সাধারণত পার্শ্ব (side) বলা হয়।
আপনাকে একটি অনির্দেশিত গ্রাফ দেওয়া হয়েছে। এটি বাইপার্টাইট কিনা যাচাই করুন, এবং যদি হয়, তার পার্শ্বগুলো আউটপুট করুন।
অ্যালগরিদম#
একটি উপপাদ্য আছে যেটি দাবি করে যে একটি গ্রাফ বাইপার্টাইট হয় যদি এবং কেবল যদি এর সমস্ত সাইকেলের দৈর্ঘ্য জোড় হয়। তবে, বাস্তবে সংজ্ঞার একটি ভিন্ন রূপ ব্যবহার করা বেশি সুবিধাজনক: একটি গ্রাফ বাইপার্টাইট হয় যদি এবং কেবল যদি এটি দুই-রঙে রঙ করা যায়।
আসুন একটি ধারাবাহিক ব্রেডথ-ফার্স্ট সার্চ ব্যবহার করি, এখনো পরিদর্শন করা হয়নি এমন প্রতিটি ভার্টেক্স থেকে শুরু করে। প্রতিটি সার্চে, যে ভার্টেক্স থেকে শুরু করি তাকে পার্শ্ব ১-এ নির্ধারণ করি। যতবার আমরা এক পার্শ্বে নির্ধারিত একটি ভার্টেক্সের এখনো অপরিদর্শিত প্রতিবেশীতে যাই, আমরা তাকে অন্য পার্শ্বে নির্ধারণ করি। যখন আমরা এক পার্শ্বে নির্ধারিত একটি ভার্টেক্সের প্রতিবেশীতে যাওয়ার চেষ্টা করি যেটি ইতিমধ্যে পরিদর্শিত, তখন আমরা পরীক্ষা করি যে এটি অন্য পার্শ্বে নির্ধারিত হয়েছে কিনা; যদি এটি একই পার্শ্বে নির্ধারিত হয়ে থাকে, আমরা সিদ্ধান্তে আসি যে গ্রাফটি বাইপার্টাইট নয়। একবার আমরা সমস্ত ভার্টেক্স পরিদর্শন করে সফলভাবে তাদের পার্শ্বে নির্ধারণ করলে, আমরা জানি যে গ্রাফটি বাইপার্টাইট এবং আমরা এর বিভাজন তৈরি করেছি।
ইমপ্লিমেন্টেশন#
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;