Đường đi Euler

Đường đi Euler là một đường đi trong đồ thị đi qua mỗi cạnh đúng một lần (các đỉnh có thể lặp lại). Chu trình Euler là đường đi Euler có đỉnh đầu trùng đỉnh cuối. Bài toán cốt lõi: cho một đồ thị, hãy kiểm tra có tồn tại đường đi/chu trình Euler hay không, và nếu có thì xây dựng ra một đường đi cụ thể.

Cách ngây thơ — thử mọi thứ tự cạnh bằng quay lui — mất tới $O(E!)$. Thuật toán Hierholzer giải trọn vẹn bài toán này trong $O(V+E)$, tức tuyến tính theo kích thước đồ thị, nhờ một mẹo đơn giản: mỗi cạnh chỉ được "tiêu thụ" đúng một lần.

Điều kiện tồn tại

Trước khi xây đường đi, ta phải kiểm tra điều kiện tồn tại. Hai điều kiện luôn cần: đồ thị phải liên thông (chỉ xét các đỉnh có cạnh) và bậc các đỉnh phải thỏa ràng buộc chẵn/lẻ.

Đồ thị vô hướng:

• Chu trình Euler: liên thông và mọi đỉnh có bậc chẵn.
• Đường đi Euler: liên thông và đúng 2 đỉnh có bậc lẻ (chúng là đỉnh đầu và đỉnh cuối); nếu có 0 đỉnh lẻ thì đó là chu trình.

Đồ thị có hướng (gọi ${\mathrm{deg}}^{+}(u)$ là bậc ra, ${\mathrm{deg}}^{-}(u)$ là bậc vào):

• Chu trình Euler: liên thông yếu và ${\mathrm{deg}}^{+}(u)={\mathrm{deg}}^{-}(u)$ với mọi đỉnh $u$.
• Đường đi Euler: liên thông yếu; đúng một đỉnh có ${\mathrm{deg}}^{+}-{\mathrm{deg}}^{-}=1$ (đỉnh đầu), đúng một đỉnh có ${\mathrm{deg}}^{-}-{\mathrm{deg}}^{+}=1$ (đỉnh cuối), tất cả đỉnh còn lại có ${\mathrm{deg}}^{+}={\mathrm{deg}}^{-}$.

Ý tưởng / Trực giác

Vì sao điều kiện bậc chẵn lại đúng? Hãy nghĩ về một đỉnh $v$ không phải đầu cũng không phải cuối của đường đi. Mỗi lần đường đi "ghé thăm" $v$, nó dùng một cạnh để đi vào và một cạnh để đi ra, tức tiêu thụ cạnh theo từng cặp. Sau khi đi qua mọi cạnh, tất cả cạnh kề $v$ phải được ghép cặp hết → bậc của $v$ phải chẵn. Hai đỉnh đầu/cuối thì lệch một cạnh (đỉnh đầu có một lần "ra" thừa, đỉnh cuối có một lần "vào" thừa) nên được phép lẻ. Đó chính là lý do "đúng 0 hoặc 2 đỉnh lẻ".

Vì sao thuật toán Hierholzer xây được đường đi? Ý tưởng: cứ đi tham lam từ đỉnh xuất phát, mỗi bước chọn một cạnh chưa dùng bất kỳ, cho tới khi kẹt (không còn cạnh chưa dùng nào ra khỏi đỉnh hiện tại). Khi điều kiện bậc thỏa mãn, ta chỉ có thể kẹt tại chính đỉnh xuất phát — vì mỗi đỉnh trung gian luôn còn một cạnh "ra" ghép cặp với cạnh vừa "vào". Lúc kẹt, ta đã có một chu trình con, nhưng có thể chưa dùng hết cạnh. Mẹo then chốt: nếu trên chu trình con đó có đỉnh $u$ vẫn còn cạnh chưa dùng, ta chèn một chu trình con mới đi từ $u$ vào giữa. Lặp lại cho tới khi hết cạnh.

Cài đặt gọn của ý tưởng "chèn chu trình con" là một DFS hậu thứ tự (post-order) trên stack: ta đi sâu hết mức theo các cạnh chưa dùng; khi một đỉnh không còn cạnh nào, ta đẩy nó vào kết quả rồi quay lui. Thứ tự đẩy vào chính là đường đi Euler đảo ngược — nên cuối cùng ta reverse lại. Để mỗi cạnh chỉ xét một lần, ta dùng con trỏ ptr[u] ghi vị trí đã duyệt trong danh sách kề của $u$: cạnh đã bỏ qua sẽ không bao giờ được xét lại.

Ví dụ chạy tay

Xét đồ thị vô hướng 4 đỉnh, các cạnh: 1-2, 2-3, 3-1, 1-4, 4-3.

        1 ----- 2
        | \     |
        |   \   |
        4 --- 3 /
   (cạnh: 1-2, 2-3, 3-1, 1-4, 4-3)

Bậc các đỉnh: $\mathrm{deg}(1)=3$, $\mathrm{deg}(2)=2$, $\mathrm{deg}(3)=3$, $\mathrm{deg}(4)=2$. Có đúng 2 đỉnh bậc lẻ là $1$ và $3$ → tồn tại đường đi Euler, bắt đầu tại một đỉnh lẻ (chọn đỉnh $1$).

Chạy DFS Hierholzer từ đỉnh $1$ (luôn lấy cạnh chưa dùng đầu tiên trong danh sách kề; [x] = cạnh đang đi):

Bước 1: tại 1, đi cạnh 1-2 →  đường hiện tại: 1 →[1-2] 2
Bước 2: tại 2, đi cạnh 2-3 →  1 → 2 →[2-3] 3
Bước 3: tại 3, đi cạnh 3-1 →  1 → 2 → 3 →[3-1] 1
Bước 4: tại 1, còn cạnh 1-4 → 1 → 2 → 3 → 1 →[1-4] 4
Bước 5: tại 4, đi cạnh 4-3 →  ... → 4 →[4-3] 3
Bước 6: tại 3 KẸT (mọi cạnh kề đã dùng) → đẩy 3 vào kết quả

Trạng thái stack đệ quy khi quay lui (post-order đẩy vào mảng path):

Thứ tự KẸT & đẩy vào path:  3, 4, 1, 3, 2, 1
                            ▲                ▲
                     đẩy trước          đẩy sau cùng

path (theo thứ tự đẩy):  [3, 4, 1, 3, 2, 1]
reverse → đường đi Euler: 1 → 2 → 3 → 1 → 4 → 3

Kiểm tra: đường 1 2 3 1 4 3 dùng các cạnh 1-2, 2-3, 3-1, 1-4, 4-3 — đúng cả 5 cạnh, mỗi cạnh một lần. Số đỉnh trong đường đi là $6=E+1$ ✓.

Cài đặt

Đồ thị vô hướng (chu trình / đường đi Euler)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m; cin >> n >> m;
    vector<vector<pair<int,int>>> adj(n + 1); // {đỉnh kề, id cạnh}
    vector<int> deg(n + 1, 0);

    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});   // cạnh vô hướng: thêm cả hai chiều, CÙNG id
        deg[u]++; deg[v]++;
    }

    // 1) Tìm đỉnh xuất phát + kiểm tra số đỉnh bậc lẻ
    int start = -1, odd = 0;
    for (int i = 1; i <= n; i++) {
        if (deg[i] % 2 == 1) { odd++; start = i; }
        if (start == -1 && deg[i] > 0) start = i; // dự phòng cho chu trình
    }
    if (odd != 0 && odd != 2) { cout << "IMPOSSIBLE\n"; return 0; }
    if (start == -1) start = 1; // đồ thị không cạnh

    // 2) Hierholzer bằng DFS lặp (tránh tràn stack khi E lớn)
    vector<bool> used(m, false);
    vector<int> ptr(n + 1, 0), path;
    stack<int> st;
    st.push(start);
    while (!st.empty()) {
        int u = st.top();
        // bỏ qua các cạnh đã dùng nhờ con trỏ ptr[u]
        while (ptr[u] < (int)adj[u].size() && used[adj[u][ptr[u]].second])
            ptr[u]++;
        if (ptr[u] == (int)adj[u].size()) {
            path.push_back(u);  // KẸT: đẩy hậu thứ tự
            st.pop();
        } else {
            auto [v, eid] = adj[u][ptr[u]++];
            used[eid] = true;   // tiêu thụ cạnh đúng MỘT lần
            st.push(v);
        }
    }
    reverse(path.begin(), path.end());

    // 3) Kiểm tra liên thông: phải dùng hết m cạnh
    if ((int)path.size() != m + 1) { cout << "IMPOSSIBLE\n"; return 0; }

    for (int x : path) cout << x << ' ';
    cout << '\n';
}

Đồ thị có hướng

Với đồ thị có hướng, mỗi cạnh chỉ thêm theo một chiều và không cần mảng used (con trỏ ptr đã đảm bảo không lặp):

vector<vector<int>> adj(n + 1); // adj[u] = các đỉnh u đi tới
vector<int> ptr(n + 1, 0), path;
// ... xây adj, tính outdeg/indeg, chọn start là đỉnh có outdeg - indeg = 1 ...

stack<int> st; st.push(start);
while (!st.empty()) {
    int u = st.top();
    if (ptr[u] < (int)adj[u].size()) {
        int v = adj[u][ptr[u]++]; // mỗi cạnh ra dùng đúng một lần
        st.push(v);
    } else {
        path.push_back(u);
        st.pop();
    }
}
reverse(path.begin(), path.end());

Độ phức tạp

• Thời gian: $O(V+E)$. Mỗi cạnh được "tiêu thụ" đúng một lần (đánh dấu used hoặc tăng ptr), và con trỏ ptr[u] chỉ tiến chứ không lùi nên tổng số lần quét toàn bộ danh sách kề trên tất cả đỉnh là $O(E)$. Mỗi đỉnh được đẩy/lấy khỏi stack tối đa số lần bằng bậc của nó, tổng cũng là $O(E)$. Cộng chi phí khởi tạo $O(V)$.
• Bộ nhớ: $O(V+E)$. Danh sách kề chiếm $O(V+E)$ (cạnh vô hướng lưu hai chiều nhưng vẫn $O(E)$), cùng các mảng deg, ptr, used và path đều $O(V+E)$. Stack tường minh sâu tối đa $O(E)$.

⚠️ Lỗi thường gặp

• Quên kiểm tra liên thông. Điều kiện bậc chẵn/lẻ là cần nhưng chưa đủ: hai tam giác rời nhau đều có mọi đỉnh bậc chẵn nhưng không có chu trình Euler chung. Luôn kiểm tra path.size() == m + 1 (đã đi hết cạnh) sau khi chạy, hoặc kiểm tra liên thông riêng. Bỏ qua bước này là lỗi phổ biến nhất.
• Dùng DFS đệ quy thường gây tràn stack. Với $E$ tới $2·{10}^5$, độ sâu đệ quy có thể bằng $E$ → stack overflow / Runtime Error. Hãy dùng DFS lặp với stack tường minh như code trên, hoặc tăng giới hạn stack.
• Quên con trỏ ptr, quét lại từ đầu danh sách kề. Nếu mỗi lần vào đỉnh $u$ lại duyệt adj[u] từ index 0 để tìm cạnh chưa dùng, độ phức tạp tụt xuống $O(E^2)$ và TLE. ptr[u] phải là biến bền vững giữa các lần ghé $u$, không reset.
• Cạnh vô hướng đánh dấu sai. Cạnh vô hướng u-v được lưu hai mục (ở adj[u] và adj[v]) nhưng cùng một id. Phải đánh dấu used theo id cạnh, không theo cặp đỉnh; nếu không, một cạnh sẽ bị đi hai lần. Đừng dùng cờ trên đỉnh thay cho cờ trên cạnh.
• Chọn sai đỉnh xuất phát ở đồ thị có hướng. Phải bắt đầu tại đỉnh có ${\mathrm{deg}}^{+}-{\mathrm{deg}}^{-}=1$. Nếu mọi đỉnh cân bằng (chu trình Euler) thì bắt đầu tại đỉnh bất kỳ có bậc > 0, tuyệt đối không bắt đầu tại đỉnh cô lập (bậc 0) — sẽ ra đường đi rỗng dù đồ thị có chu trình Euler.
• Quên reverse kết quả. Mảng path được điền theo hậu thứ tự nên là đường đi đảo ngược. Quên reverse sẽ in ra thứ tự sai (dù với chu trình thì vẫn hợp lệ, với đường đi có đầu/cuối khác nhau thì sai).

Biến thể / Mở rộng

• Bài toán người đưa thư Trung Hoa (Chinese Postman): tìm chu trình ngắn nhất đi qua mọi cạnh (cạnh được phép đi lại) trên đồ thị có trọng số. Khi đồ thị chưa có chu trình Euler, ta nhân đôi (ghép cặp) các đỉnh bậc lẻ với chi phí nhỏ nhất rồi mới tìm chu trình Euler.
• Dãy De Bruijn: xây chuỗi ngắn nhất chứa mọi xâu độ dài $k$ trên bảng chữ cái cho trước — quy về tìm chu trình Euler trên đồ thị De Bruijn (đỉnh là các xâu độ dài $k-1$).
• Ghép gen (DNA assembly), bài toán vẽ một nét không nhấc bút đều là ứng dụng trực tiếp của đường đi Euler.

Bài tập luyện

• Giao Thư (maildeliv) — (Nâng cao) Tìm chu trình Euler trên đồ thị vô hướng bắt đầu/kết thúc tại đỉnh 1, hoặc báo IMPOSSIBLE — áp dụng trực tiếp Hierholzer + kiểm tra bậc chẵn và liên thông.
• Dãy De Bruijn (debruijn) — (Kỳ cựu) Dựng chuỗi nhị phân ngắn nhất chứa mọi xâu độ dài $n$; mô hình hóa thành chu trình Euler trên đồ thị De Bruijn có hướng — bài kinh điển về ứng dụng Euler.
• Đồ Thị Con Euler (eulersub) — (Nâng cao) Đếm số tập con cạnh sao cho mọi đỉnh có bậc chẵn (modulo ${10}^9+7$); luyện hiểu sâu tính chất bậc chẵn — nền tảng lý thuyết của đường đi Euler.