Eulerian Path

Điều kiện bậc

Mỗi lần hành trình đi qua một đỉnh, nó dùng một cạnh vào và một cạnh ra. Vì vậy:

• Vô hướng. Có chu trình Euler khi và chỉ khi mọi đỉnh có bậc chẵn và mọi cạnh nằm trong cùng một thành phần liên thông. Có đường đi Euler khi đúng 0 hoặc 2 đỉnh có bậc lẻ; hai đỉnh lẻ là hai đầu đường.
• Có hướng. Có chu trình Euler khi mọi đỉnh có bậc vào bằng bậc ra và các cung liên thông (khi bỏ hướng). Có đường đi từ $s$ tới $t$ khi $\mathrm{out}(s) = \mathrm{in}(s) + 1$, $\mathrm{in}(t) = \mathrm{out}(t) + 1$, mọi đỉnh khác cân bằng.

Điều kiện “liên thông” chỉ xét các đỉnh có cạnh; đỉnh cô lập không cản trở. Khi cài, cách kiểm liên thông đơn giản nhất là dựng hành trình rồi xem nó có đủ $m$ cạnh không.

Ví dụĐồ Thị Khép Kín

Đề. Nhiều đồ thị vô hướng tới khi gặp số 0, mỗi đồ thị $n \le 999$ đỉnh. In 1 nếu có chu trình Euler và cả $n$ đỉnh liên thông, ngược lại 0.

Lời giải. Có chu trình Euler khi mọi bậc chẵn và các cạnh nằm chung một thành phần. Bài này còn đòi cả $n$ đỉnh liên thông, nên đỉnh cô lập cũng làm hỏng điều kiện.

Bước 1: đếm bậc và gộp thành phần. Mỗi cạnh vừa tăng bậc hai đầu, vừa hợp hai đầu trong DSU; comps giảm mỗi lần hợp được.

deg[u]++;
deg[v]++;
u = find(u), v = find(v);
if (u != v) par[u] = v, comps--;

Bước 2: kiểm. comps == 1 là cả $n$ đỉnh liên thông; đỉnh không có cạnh làm comps lớn hơn 1, đúng yêu cầu.

bool ok = comps == 1;
for (ll i = 1; i <= n; i++)
    if (deg[i] % 2) ok = 0;

Mỗi đồ thị đặt lại par và deg trên $1..n$.

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

const ll N = 1005;
ll n, m, par[N], deg[N];

ll find(ll u) {
    return par[u] == u ? u : par[u] = find(par[u]);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    while (cin >> n && n) {
        cin >> m;
        for (ll i = 1; i <= n; i++) par[i] = i, deg[i] = 0;
        ll comps = n;
        for (ll i = 1; i <= m; i++) {
            ll u, v;
            cin >> u >> v;
            deg[u]++;
            deg[v]++;
            u = find(u), v = find(v);
            if (u != v) par[u] = v, comps--;
        }
        bool ok = comps == 1;
        for (ll i = 1; i <= n; i++)
            if (deg[i] % 2) ok = 0;
        cout << ok << '\n';
    }
}

ChạyInput3 3
1 2
2 3
3 1
4 3
1 2
2 3
3 1
0

Output1
0

Mỗi đồ thị $O((n + m)\,\alpha(n))$.

Hierholzer

Đi từ đỉnh xuất phát theo các cạnh chưa dùng cho tới khi kẹt. Ở đồ thị thỏa điều kiện, chỗ kẹt chính là điểm xuất phát, và ta có một chu trình. Nếu còn cạnh chưa dùng, chúng gắn vào một đỉnh nào đó trên chu trình: chèn một chu trình con tại đó.

Hierholzer làm việc chèn này tự động bằng một ngăn xếp. Đỉnh trên cùng còn cạnh chưa dùng thì đi tiếp theo cạnh đó; hết cạnh thì đưa nó vào kết quả và bỏ khỏi ngăn xếp. Kết quả thu được là hành trình viết ngược, đảo lại là xong.

Hình dưới chạy từng bước: cạnh xanh đã dùng, đỉnh xanh dương đang nằm trên ngăn xếp.

Mỗi đỉnh giữ con trỏ ptr[u] tới cạnh kế tiếp trong danh sách kề. Cạnh vô hướng nằm ở hai danh sách nên đánh dấu used theo chỉ số cạnh. Mỗi cạnh được xét hai lần, tổng $O(n + m)$. Dùng ngăn xếp tường minh để khỏi đệ quy sâu $m$ tầng.

Ví dụHành Trình Qua Mọi Cạnh

Đề. Đa đồ thị vô hướng $n \le 10^5$, $m \le 2 \cdot 10^5$. In chu trình qua mỗi cạnh đúng một lần, bắt đầu và kết thúc ở 1, hoặc IMPOSSIBLE.

Lời giải. Bậc lẻ ở đâu đó thì vô nghiệm. Ngược lại chạy Hierholzer từ 1; hành trình dài khác $m + 1$ nghĩa là có cạnh không tới được từ 1, cũng vô nghiệm.

Bước 1: danh sách kề chứa chỉ số cạnh. Một cạnh vô hướng nằm ở hai danh sách; đi theo nó từ một đầu thì đầu kia phải thấy nó đã dùng. Lưu chỉ số cạnh (không phải đỉnh kề) để đánh dấu used theo cạnh. Khuyên và cạnh song song cũng được xử lý đúng.

cin >> eu[i] >> ev[i];
g[eu[i]].push_back(i);
g[ev[i]].push_back(i);

Bước 2: Hierholzer bằng ngăn xếp. ptr[u] là con trỏ trong danh sách của $u$, bỏ qua các cạnh đã dùng; con trỏ chỉ tăng nên tổng công $O(n + m)$. Đỉnh trên cùng còn cạnh thì đi tiếp; hết cạnh thì đưa vào path và bỏ ra.

while (!st.empty()) {
    ll u = st.back();
    while (ptr[u] < (ll)g[u].size() && used[g[u][ptr[u]]]) ptr[u]++;
    if (ptr[u] == (ll)g[u].size()) {
        path.push_back(u);
        st.pop_back();
    } else {
        ll e = g[u][ptr[u]];
        used[e] = 1;
        st.push_back(eu[e] == u ? ev[e] : eu[e]);
    }
}

Bước 3: kiểm và in. path là hành trình viết ngược, đảo lại là xong. path.size() != m + 1 thì có cạnh không đi tới được.

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

const ll N = 1e5 + 5, M = 2e5 + 5;
ll n, m, eu[M], ev[M], used[M], ptr[N];
vector<ll> g[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        cin >> eu[i] >> ev[i];
        g[eu[i]].push_back(i);
        g[ev[i]].push_back(i);
    }
    for (ll u = 1; u <= n; u++)
        if (g[u].size() % 2) {
            cout << "IMPOSSIBLE\n";
            return 0;
        }
    vector<ll> st = {1}, path;
    while (!st.empty()) {
        ll u = st.back();
        while (ptr[u] < (ll)g[u].size() && used[g[u][ptr[u]]]) ptr[u]++;
        if (ptr[u] == (ll)g[u].size()) {
            path.push_back(u);
            st.pop_back();
        } else {
            ll e = g[u][ptr[u]];
            used[e] = 1;
            st.push_back(eu[e] == u ? ev[e] : eu[e]);
        }
    }
    if ((ll)path.size() != m + 1) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    reverse(path.begin(), path.end());
    for (ll v : path) cout << v << ' ';
    cout << '\n';
}

ChạyInput4 4
1 2
2 3
3 4
4 1

Output1 2 3 4 1

$O(n + m)$.

Ví dụTừ Một Đến Đích Qua Mọi Cung

Đề. Đa đồ thị có hướng $n \le 10^5$, $m \le 2 \cdot 10^5$. In đường đi qua mỗi cung đúng một lần, từ 1 tới $n$, hoặc IMPOSSIBLE.

Lời giải. Đường Euler từ 1 tới $n$ cần: đỉnh 1 thừa một cung ra, đỉnh $n$ thừa một cung vào, mọi đỉnh khác cân bằng. Rồi chạy Hierholzer từ 1 trên cung có hướng; thiếu cung trong hành trình thì vô nghiệm.

Bước 1: kiểm bậc.

bool ok = out[1] - in[1] == 1 && in[n] - out[n] == 1;
for (ll u = 2; u < n; u++)
    if (in[u] != out[u]) ok = 0;

Bước 2: Hierholzer. g[u] chứa đỉnh đích, và mỗi cung chỉ nằm ở danh sách của đầu xuất phát, nên chỉ cần con trỏ ptr[u]++, không cần đánh dấu. Đường đi kết thúc tự nhiên ở $n$, đỉnh duy nhất có thể kẹt trước khi hết cung.

while (!st.empty()) {
    ll u = st.back();
    if (ptr[u] == (ll)g[u].size()) {
        path.push_back(u);
        st.pop_back();
    } else st.push_back(g[u][ptr[u]++]);
}

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

const ll N = 1e5 + 5;
ll n, m, in[N], out[N], ptr[N];
vector<ll> g[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back(v);
        out[u]++;
        in[v]++;
    }
    bool ok = out[1] - in[1] == 1 && in[n] - out[n] == 1;
    for (ll u = 2; u < n; u++)
        if (in[u] != out[u]) ok = 0;
    if (!ok) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    vector<ll> st = {1}, path;
    while (!st.empty()) {
        ll u = st.back();
        if (ptr[u] == (ll)g[u].size()) {
            path.push_back(u);
            st.pop_back();
        } else st.push_back(g[u][ptr[u]++]);
    }
    if ((ll)path.size() != m + 1) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    reverse(path.begin(), path.end());
    for (ll v : path) cout << v << ' ';
    cout << '\n';
}

ChạyInput4 3
1 2
2 3
3 4

Output1 2 3 4

$O(n + m)$.

Danh sách kề dạng vector cho mỗi đỉnh là cách quen tay, nhưng với đồ thị lớn nó có giá:

Mảng liên kết (head, nxt, to) nhanh hơn vector khoảng 4 lần, vì không cấp phát bộ nhớ riêng cho từng đỉnh. Đồ thị cỡ triệu cạnh mà thời gian sát giới hạn thì đáng đổi.

Nhỏ nhất theo từ điển

Sắp danh sách kề của mỗi đỉnh tăng dần rồi chạy Hierholzer: ta được đường đi Euler có dãy đỉnh nhỏ nhất theo từ điển.

Lý do: mỗi bước ngăn xếp luôn đi theo cung nhỏ nhất còn lại. Nếu cung đó dẫn vào một nhánh “cụt” (quay về sớm), nhánh ấy được ghi vào kết quả sau cùng tại vị trí của nó, đúng chỗ mà một đường tối ưu cũng phải để nó. Đỉnh xuất phát là đỉnh có $\mathrm{out} = \mathrm{in} + 1$ nếu có, không thì đỉnh nhỏ nhất có cung ra.

Ví dụĐường Đi Có Hướng Nhỏ Nhất

Đề. Đa đồ thị có hướng $n \le 10^5$, $m \le 2 \cdot 10^5$ (có cung song song và khuyên), bỏ hướng thì liên thông. In đường đi Euler nhỏ nhất theo từ điển, hoặc No.

Lời giải. Kiểm bậc: không quá một đỉnh có $\mathrm{out} - \mathrm{in} = 1$, không quá một đỉnh có $\mathrm{in} - \mathrm{out} = 1$, còn lại cân bằng. Để được đường nhỏ nhất theo từ điển, sắp danh sách kề rồi chạy Hierholzer: luôn đi cung nhỏ nhất còn lại trước. Nhánh nào quay về sớm được đưa vào kết quả sau, đúng vị trí nó phải đứng trong đường tối ưu.

Bước 1: sắp và đếm hiệu bậc. Hiệu khác $0, \pm 1$ thì đặt plus = 5 để chắc chắn bị loại. Hai số đếm phải cùng là 0 hoặc cùng là 1.

for (ll u = 1; u <= n; u++) {
    sort(g[u].begin(), g[u].end());
    ll d = out[u] - in[u];
    if (d == 1) plus++, s = u;
    else if (d == -1) minus++;
    else if (d != 0) plus = 5;
}

Bước 2: chọn đỉnh đầu. Không có đỉnh hiệu $+1$ thì đường là chu trình, bắt đầu ở đỉnh nhỏ nhất có cung ra.

if (!s)
    for (ll u = 1; u <= n && !s; u++)
        if (out[u]) s = u;

Bước 3: Hierholzer như ví dụ trước. Đề bảo đảm bỏ hướng thì liên thông, nhưng vẫn kiểm path.size() == m + 1 cho chắc.

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

const ll N = 1e5 + 5;
ll n, m, in[N], out[N], ptr[N];
vector<ll> g[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back(v);
        out[u]++;
        in[v]++;
    }
    ll s = 0, plus = 0, minus = 0;
    for (ll u = 1; u <= n; u++) {
        sort(g[u].begin(), g[u].end());
        ll d = out[u] - in[u];
        if (d == 1) plus++, s = u;
        else if (d == -1) minus++;
        else if (d != 0) plus = 5;
    }
    if (plus > 1 || minus > 1 || plus != minus) {
        cout << "No\n";
        return 0;
    }
    if (!s)
        for (ll u = 1; u <= n && !s; u++)
            if (out[u]) s = u;
    vector<ll> st = {s}, path;
    while (!st.empty()) {
        ll u = st.back();
        if (ptr[u] == (ll)g[u].size()) {
            path.push_back(u);
            st.pop_back();
        } else st.push_back(g[u][ptr[u]++]);
    }
    if ((ll)path.size() != m + 1) {
        cout << "No\n";
        return 0;
    }
    reverse(path.begin(), path.end());
    for (ll v : path) cout << v << ' ';
    cout << '\n';
}

ChạyInput4 5
1 2
1 3
2 1
3 4
4 1

Output1 2 1 3 4 1

$O(n + m \log m)$ vì phải sắp.

Quy về Euler

Đồ thị de Bruijn. Cần xâu nhị phân ngắn nhất chứa mọi mẫu dài $n$. Coi mỗi mẫu $n$ bit là một cạnh nối $(n - 1)$ bit đầu với $(n - 1)$ bit cuối của nó. Mỗi đỉnh có đúng hai cung ra và hai cung vào, nên có chu trình Euler qua cả $2^n$ cạnh.

Đọc bit cuối của mỗi cạnh theo thứ tự đi, đặt sau $n - 1$ bit 0 của đỉnh đầu, ta được xâu dài $2^n + n - 1$. Không thể ngắn hơn, vì mỗi ký tự thêm chỉ tạo ra một cửa sổ mới.

Khôi phục dãy từ các cặp kề. Các cặp kề nhau của một dãy là các cạnh của đường đi qua dãy đó, nên dãy chính là đường đi Euler. Nén giá trị, chọn đỉnh bậc lẻ làm đầu, rồi đi theo cạnh chưa dùng.

Ví dụPhủ Đủ Mọi Mẫu Nhị Phân

Đề. Với $n \le 15$, in một xâu nhị phân ngắn nhất chứa mọi xâu nhị phân dài $n$.

Lời giải. Đồ thị de Bruijn: đỉnh là số $n - 1$ bit, cung từ $u$ theo bit $b$ tới $(2u + b) \bmod 2^{n-1}$. Mỗi cung ứng với đúng một mẫu $n$ bit, mỗi đỉnh có 2 cung vào và 2 cung ra, nên có chu trình Euler. Đi chu trình đó từ đỉnh 0 rồi ghi các bit đã đi là xong. $n = 1$ có một đỉnh với hai khuyên, vẫn đúng.

Bước 1: Hierholzer có nhớ bit. mask giữ $n - 1$ bit cuối; ptr[u] đếm số cung ra đã dùng (0, 1 hoặc 2), thử bit 0 trước. Mỗi phần tử ngăn xếp nhớ bit của cung đã đi vào nó; khi lùi thì ghi bit đó. Điểm xuất phát có bit $-1$, không ghi.

while (!st.empty()) {
    ll u = st.back().first;
    if (ptr[u] < 2) {
        ll b = ptr[u]++;
        st.push_back({((u << 1) | b) & mask, b});
    } else {
        if (st.back().second >= 0) bits += char('0' + st.back().second);
        st.pop_back();
    }
}

Bước 2: ghép xâu. Đảo bits được bit cuối của các cung theo thứ tự đi. Đặt sau $n - 1$ bit 0 của đỉnh xuất phát thì mỗi cửa sổ $n$ bit là đúng một cung, tức đúng một mẫu.

reverse(bits.begin(), bits.end());
cout << string(n - 1, '0') << bits << '\n';

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

ll n, ptr[1 << 15];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    ll V = 1 << (n - 1), mask = V - 1;
    vector<pair<ll, ll>> st = {{0, -1}};
    string bits;
    while (!st.empty()) {
        ll u = st.back().first;
        if (ptr[u] < 2) {
            ll b = ptr[u]++;
            st.push_back({((u << 1) | b) & mask, b});
        } else {
            if (st.back().second >= 0) bits += char('0' + st.back().second);
            st.pop_back();
        }
    }
    reverse(bits.begin(), bits.end());
    cout << string(n - 1, '0') << bits << '\n';
}

ChạyInput3

Output0001011100

$O(2^n)$, xâu dài $2^n + n - 1$.