Graph-ын бүх edge-ээр яг нэг удаа явах path-ыг олох арга. Харандаагаа өргөлгүй зурахтай адил.

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

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

4 node, edge нь 1-2, 2-3, 3-1, 3-4. Бүх edge-ээр яг нэг удаа явж болох уу?

Зэрэг нь: node 1 нь 2, node 2 нь 2, node 3 нь 3, node 4 нь 1. Сондгой зэрэгтэй node яг хоёр (3 ба 4), тэгэхээр path бий. Node 3-аас эхэлж node 4 дээр дуусна: 3 2 1 3 4.

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

Энгийн арга бол edge-ийн бүх дарааллыг шалгах. m = 12 бол 479 сая гаруй дараалал.

Hierholzer-ийн санаа: эхлэл node-оос ашиглаагүй edge-ээр гацтал явна. Гацсан node-ыг path-т бичээд нэг алхам ухарна. Ухарсан node-оос ашиглаагүй edge гарвал тэндээс дахин гацтал явна. Ингэж жижиг cycle-уудыг үндсэн path-т "залгаж" явна. Path урвуу дарааллаар бичигддэг тул эцэст нь урвуулна.

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

Euler path
Graph-ын бүх edge-ээр яг нэг удаа явах path. Эхэлсэн node дээрээ дуусвал Euler cycle.
deg[u]
Node u-д залгагдсан edge-ийн тоо (зэрэг).
ptr[u]
g[u]-гийн аль хүртэлх edge-ийг аль хэдийн харсан бэ. Ингэснээр edge бүрийг нэг л удаа шалгана.
used[id]
id дугаартай edge-ийг ашигласан эсэх. Чиглэлгүй edge хоёр node-ын жагсаалтад хоёуланд нь байдаг.
path
Гацсан дарааллаараа бичигдсэн node-ууд. Урвуулбал хариу.
1deg=22deg=43deg=44deg=35deg=3
алхсан edge = 0 / 8
дуудлагын stack
хоосон
path — урвуу дарааллаар
хоосон

Бүх edge-ээр яг нэг удаа явах path хайна. Харандаагаа өргөлгүй зурахтай адил. Node доорх deg нь тухайн node-д хэдэн edge залгагдсаныг заана.

Алхам 1 / 20
Хурд
  • Сондгой зэрэгтэй node
  • Одоо байгаа node
  • Сая алхсан edge
  • Алхсан, path-т хараахан ороогүй
  • Path-т орсон edge
Слайд 1 / 7

Харандаагаа өргөлгүй

Энэ захидлын дугтуйг харандаагаа өргөлгүй, нэг шугамыг хоёр давхарлалгүй зурж болох уу? Бүх edge-ээр яг нэг удаа явах path-ыг Euler path гэнэ.

eulerian-path.cpp
#include <bits/stdc++.h>
using namespace std;
int n, m, deg[100005], ptr[100005];
bool used[200005];
vector<pair<int, int>> g[100005];
vector<int> path;
void go(int u) {
while (ptr[u] < (int)g[u].size()) {
auto [v, id] = g[u][ptr[u]++];
if (!used[id]) {
used[id] = true;
go(v);
}
}
path.push_back(u);
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back({v, i});
g[v].push_back({u, i});
deg[u]++;
deg[v]++;
}
int s = 1, odd = 0;
for (int i = n; i >= 1; i--) if (deg[i] > 0) s = i;
for (int i = n; i >= 1; i--) {
if (deg[i] % 2 == 1) {
odd++;
s = i;
}
}
if (odd <= 2) {
go(s);
}
if ((int)path.size() != m + 1) {
cout << "NO\n";
} else {
for (int i = m; i >= 0; i--) cout << path[i] << ' ';
}
return 0;
}

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

Edge бүрийг нэг л удаа дайрах path эсвэл cycle олно. Домино өрөх, string-үүдийг гинжлэх, De Bruijn дараалал зэрэг олимпиадын бодлогод гардаг.

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

1. Node бүрийн зэргийг (deg) тоолно. Сондгой зэрэгтэй node 0 эсвэл 2 байх ёстой. 2. Сондгой зэрэгтэй node байвал түүнээс, үгүй бол edge-тэй аль нэг node-оос эхэлнэ. 3. go(u) дуудлага: u дээрээс гарах ашиглаагүй edge бүрээр явж, edge-ийг ашигласан гэж тэмдэглээд go(v) дуудна. 4. u дээр явах edge үлдээгүй болмогц u-г path-т нэмнэ. 5. Path m + 1 урттай бол урвуулж хэвлэнэ, үгүй бол graph тасархай тул NO. Оролт: n m, дараа нь m мөрөнд «u v» (чиглэлгүй edge).

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

Path-ын дундах node-оор дайрч өнгөрөх бүрт орох, гарах хоёр edge хэрэглэнэ. Тиймээс эхлэл ба төгсгөлөөс бусад node-ын зэрэг тэгш байх ёстой: сондгой node 0 эсвэл 2. Код энэ нөхцөл хангагдвал go(s)-ийг дуудна. go нь edge бүрийг яг нэг удаа ашигладаг, path-д m + 1 node орсон бол бүх edge хамрагдсан гэсэн үг. Үгүй бол graph тасархай.

ptr ашигладаг тул g[u]-г нэг л удаа гүйнэ. Хугацаа O(n + m).

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

  • Сондгой node байхад node 1-ээс эхлэх. Сондгой node байвал заавал түүнээс эхэлнэ.
  • ptr-гүйгээр loop-ыг дахин дахин эхнээс нь гүйлгэх. Олон edge-тэй node дээр O(m²) болно.
  • Чиглэлгүй edge-ийг хоёр талаас нь тусдаа тэмдэглэх. Нэг edge нэг id-тай байж, нэг used-аар хоёр тал хоёулаа хаагдах ёстой.
  • Graph холбоотой эсэхийг шалгахгүй байх. Зэрэг зөв байсан ч хоёр тусдаа cycle байж болно. Код path-ын уртаар шалгадаг.

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

  • Бүх зэрэг тэгш: Euler cycle гарна, эхэлсэн node дээрээ дуусна.
  • Сондгой node 4: хариу NO, go огт дуудагдахгүй.
  • Хоёр тусдаа triangle: бүх зэрэг тэгш ч path нь 3 edge-ээр л явж чадна, хариу NO.

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

  1. Triangle 1-2, 2-3, 3-1 дээр код юу хэвлэх вэ?

    Хариу харах

    1 2 3 1. Бүх зэрэг тэгш тул node 1-ээс эхэлж, node 1 дээр дуусна.

  2. 1-2, 1-3, 1-4 star-д Euler path байх уу?

    Хариу харах

    Үгүй. Node 1 нь 3, бусад нь 1 зэрэгтэй: сондгой node 4 байна.

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

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

  1. 1.Animation-ы "захидлын дугтуй" жишээн дээр (1 2, 1 3, 2 3, 2 4, 2 5, 3 4, 3 5, 4 5) хариу ямар node-оос эхэлж, ямар node дээр дуусах вэ?

    Hint харах

    Node бүрийн зэргийг тоол.

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

    Сондгой зэрэгтэй нь node 4, 5. Код хамгийн бага сондгой node 4-өөс эхэлнэ: 4 2 1 3 2 5 3 4 5, node 5 дээр дуусна.

  2. 2.Чиглэлтэй graph-т Euler path олдог болго.

    Hint харах

    Чиглэлтэй graph-т сондгой зэргийн оронд орох ба гарах edge-ийн тоог харьцуулна.

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

    out[u] - in[u] = 1 байх node эхлэл, in[u] - out[u] = 1 байх node төгсгөл, бусад нь тэнцүү байх ёстой. g[u]-д зөвхөн u → v-г нэмж, used хэрэггүй (ptr хангалттай). Үлдсэн go(u) ижил.

  3. 3.Домино бүр хоёр тоотой (0–6). Бүх доминог ижил тоог нь залгаж нэг эгнээнд өрж болох эсэхийг шийд.

    Hint харах

    Тоо бүр node, домино бүр edge.

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

    7 node-той graph байгуулж, домино a b бүрийг a-b edge болгоно. Euler path байвал өрж болно. Path-ын дараалал нь доминог өрөх дараалал.

Жишээ

Оролт

5 8
1 2
1 3
2 3
2 4
2 5
3 4
3 5
4 5

Гаралт

4 2 1 3 2 5 3 4 5