Node-уудыг хоёр өнгөөр будаж, edge бүр хоёр өөр өнгийн node-ыг холбож чадах эсэхийг BFS-ээр шалгах арга.

IntermediateХугацаа: O(n + m)Санах ой: O(n + m)

Эхлээд жижиг бодлого

4 node-той square: 1-2, 2-3, 3-4, 4-1. Node 1, 3-ыг нэг багт, node 2, 4-ийг нөгөө багт оруулбал edge бүр хоёр өөр багийг холбоно. Хариу YES.

Харин triangle 1-2, 2-3, 3-1 дээр node 1 ба 2 өөр багт, node 2 ба 3 өөр багт орвол node 1, 3 нэг багт таарна. Гэтэл тэд edge-ээр холбоотой. Хариу NO.

Энгийн аргаас санаа руу

Энгийн арга бол node бүрийг хоёр багийн аль нэгэнд оруулах бүх 2ⁿ хувилбарыг шалгах. n = 30 бол тэрбум гаруй хувилбар.

Гол санаа: нэг node-ын багийг сонгомогц түүний хөршүүдийн баг шууд тодорхой болно: эсрэг баг. Тиймээс BFS-ээр явж хөрш бүрийг эсрэг өнгөөр будна. Нэг edge-ийн хоёр үзүүр ижил өнгөтэй болчихвол хуваах боломжгүй.

Нэр томьёо ба тэмдэглэгээ

bipartite graph
Node-уудыг хоёр багт хувааж, edge бүр хоёр өөр багийн node-ыг холбодог graph.
col[u]
Node u-гийн өнгө: -1 бол хараахан будаагүй, 0 эсвэл 1 бол баг.
1 - col[u]
Эсрэг өнгө: 0 бол 1, 1 бол 0.
q
BFS-ийн queue. Будсан ч хөршийг нь хараахан шалгаагүй node-ууд энд хүлээнэ.
123456
q (queue)
хоосон

Node-уудыг хоёр багт хуваая: col = 0 ба col = 1. Edge бүр хоёр өөр багийн node-ыг холбох ёстой. Тиймээс хөрш бүрийг өөрийнхөөс нь эсрэг багт оруулна.

Алхам 1 / 26
Хурд
  • col = 0
  • col = 1
  • Одоогийн node / edge
  • Сая будсан / зөрчил
Слайд 1 / 6

Хоёр баг

Ангийнхаа хүүхдүүдийг хоёр багт хуваая. Найз хоёр нэг багт орж болохгүй. Edge бүр нэг хос найзыг заана.

bipartite-check.cpp
#include <bits/stdc++.h>
using namespace std;
int n, m, col[100005];
vector<int> g[100005];
queue<int> q;
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; i++) col[i] = -1;
for (int s = 1; s <= n; s++) {
if (col[s] != -1) continue;
col[s] = 0;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : g[u]) {
if (col[v] == -1) {
col[v] = 1 - col[u];
q.push(v);
} else if (col[v] == col[u]) {
cout << "NO\n";
return 0;
}
}
}
}
cout << "YES\n";
return 0;
}

Юунд хэрэгтэй вэ?

Хүмүүсийг хоёр багт хуваах, ажлыг хоёр ээлжинд хуваах зэрэг бодлогод хэрэгтэй. Graph хоёр багт хуваагдана гэдэг нь сондгой урттай cycle байхгүй гэсэн үг.

Яаж ажилладаг вэ?

1. Эхэндээ бүх node өнгөгүй: col[i] = -1. 2. Өнгөгүй node s олдвол col[s] = 0 болгоод queue-д хийнэ. 3. Queue-гээс node u гаргаж, хөрш бүрийг шалгана. 4. Хөрш v өнгөгүй бол col[v] = 1 - col[u] болгоод queue-д нэмнэ. 5. Хөрш v, node u хоёр ижил өнгөтэй бол хоёр багт хуваагдахгүй. Хариу NO. 6. Бүх node будагдаж, зөрчил гараагүй бол YES. Оролт: n m, дараа нь m мөрөнд «u v» (чиглэлгүй edge).

Яагаад зөв, хэр хурдан бэ?

Component-ын эхний node-ын өнгийг сонгосны дараа бусад бүх node-ын өнгө албаар тодорхой болно. Тиймээс BFS-ийн будсан өнгө бол цорын ганц боломжит будалт. Энэ будалтад зөрчил гарвал ямар ч будалтад гарна, хариу NO. Зөрчил гараагүй бол будалт өөрөө хариу.

Энэ нь "graph-т сондгой урттай cycle байхгүй" гэсэнтэй яг адил. Сондгой cycle-ыг тойрч ээлжлэн будахад эхний ба сүүлийн node ижил өнгөтэй таардаг. Хугацаа O(n + m), n = 100 000 дээр шууд ажиллана.

Түгээмэл алдаа

  • Зөвхөн node 1-ээс BFS эхлүүлэх. Graph хэд хэдэн component-той бол бусад component шалгагдахгүй. Код for (int s = 1; s <= n; s++) гэж бүх node-оос эхлүүлж үздэг.
  • col-ыг 0-ээр эхлүүлэх. Тэгвэл "будаагүй" ба "0 өнгөтэй" ялгагдахгүй. -1 ашигла.
  • Зөрчил олдмогц хариугаа хэвлээд зогсохоо мартах. Цааш явбал NO, YES хоёулаа хэвлэгдэж магадгүй.

Хязгаарын тохиолдол

  • Edge байхгүй: бүх node col = 0 болно, хариу YES.
  • Tree: cycle огт байхгүй тул үргэлж YES.
  • Тэгш урттай cycle (4, 6 node) YES, сондгой урттай cycle (3, 5 node) NO.

Өөрийгөө шалга

  1. 5 node-той cycle 1-2-3-4-5-1 хоёр багт хуваагдах уу?

    Хариу харах

    Үгүй, NO. Урт нь 5 буюу сондгой.

  2. Tree яагаад үргэлж хоёр багт хуваагддаг вэ?

    Хариу харах

    Tree-д cycle байхгүй, тэр тусмаа сондгой cycle байхгүй. Root-оос тэгш зайтай node-уудыг нэг багт, сондгой зайтайг нөгөөд оруулахад хангалттай.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.4 node, edge нь 1-2, 2-3, 3-4, 4-2. Код ямар edge дээр зөрчил олж, юу хэвлэх вэ?

    Hint харах

    col[1] = 0-ээс эхэлж, queue-гээс гарах дарааллыг дага.

    Хариу ба тайлбар

    Node 2 col = 1, node 3, 4 хоёулаа col = 0 болно. Node 3-ыг queue-гээс гаргахад хөрш 4 мөн col = 0 тул 3-4 edge дээр зөрчил гарна. Хариу NO. 2, 3, 4 нь triangle үүсгэж байгаа.

  2. 2.Хариу YES бол хоёр багийн node-уудыг тус тусад нь хэвлэдэг болго.

    Hint харах

    Бүх BFS дууссаны дараа col array бэлэн байгаа.

    Хариу ба тайлбар

    YES хэвлэсний дараа col[i] = 0 байх i-г нэг мөрөнд, col[i] = 1 байх i-г дараагийн мөрөнд хэвлэнэ.

  3. 3.Graph bipartite бол нэг багт хамгийн ихдээ хэдэн node оруулж болох вэ? Component бүрт аль багийг нь "том баг" гэж сонгож болно.

    Hint харах

    Component бүрийн хоёр талыг сольж болно, бусад component-д нөлөөлөхгүй.

    Хариу ба тайлбар

    Component бүрт 0 ба 1 өнгийн node-ыг тоолоод их талыг нь авна. Бүх component-ын эдгээр утгын нийлбэр хариу болно.

Жишээ

Оролт

6 6
1 2
1 4
2 3
3 6
4 5
5 6

Гаралт

YES