Хоёр хэсэгт граф шалгах¶
Хоёр хэсэгт граф гэдэг нь ирмэг бүр нь өөр өөр олонлогийн хоёр оройг холбохоор (өөрөөр хэлбэл нэг олонлогийн оройг холбох ирмэг байхгүй) оройнуудыг нь огтлолцолгүй хоёр олонлог болгон хувааж болох граф юм. Эдгээр олонлогийг ихэвчлэн тал гэж нэрлэдэг.
Танд чиглэлгүй граф өгөгдсөн. Тэр нь хоёр хэсэгт эсэхийг шалгаж, хэрэв тийм бол түүний талуудыг гарга.
Алгоритм¶
Граф зөвхөн бүх цикл нь тэгш урттай байх үед л хоёр хэсэгт байна гэж баталдаг теорем бий. Гэвч практикт тодорхойлолтын өөр томьёоллыг ашиглах нь илүү тохиромжтой: граф зөвхөн хоёр өнгөөр будаж болох үед л хоёр хэсэгт байна.
Хараахан зочлоогүй орой бүрээс эхлэн цуврал өргөнөөр эхлэх хайлт ашиглая. Хайлт бүрд бид эхлэх оройг 1-р талд оноодог. Нэг талд оноогдсон оройн хараахан зочлоогүй хөршид зочлох бүрд бид түүнийг нөгөө талд оноодог. Нэг талд оноогдсон оройн аль хэдийн зочилсон хөрш рүү явахыг оролдох үед бид тэр нь нөгөө талд оноогдсон эсэхийг шалгана; хэрэв ижил талд оноогдсон бол бид граф хоёр хэсэгт биш гэж дүгнэнэ. Бүх оройд зочилж, тэдгээрийг талуудад амжилттай оноосны дараа бид граф хоёр хэсэгт болохыг мэдэх ба түүний хуваалтыг байгуулсан болно.
Implementation¶
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;