Eulerian Path

IKhi nào có chu trình, đường đi Euler

Một đường đi Euler là một đường đi qua mỗi cạnh của đồ thị đúng một lần; được phép đi qua một đỉnh nhiều lần. Nếu đường đi đó kết thúc ở chính đỉnh xuất phát thì ta có một chu trình Euler. Bậc của một đỉnh là số cạnh nối với nó; một khuyên (cạnh nối một đỉnh với chính nó) góp $2$ vào bậc.

Cách dễ nghĩ ra nhất là quay lui (bài 0.8): thử mọi cách chọn cạnh đi tiếp. Số cách đi tăng theo cấp số nhân, nên chỉ chạy được khi đồ thị có vài chục cạnh. May mắn là chỉ cần nhìn bậc của các đỉnh là biết có chu trình hay không:

• Đồ thị 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.
• Đồ thị vô hướng có đường đi Euler khi và chỉ khi có đúng $0$ hoặc đúng $2$ đỉnh có bậc lẻ, và mọi cạnh nằm trong cùng một thành phần liên thông. Khi có hai đỉnh bậc lẻ, đường đi bắt đầu ở một đỉnh và kết thúc ở đỉnh kia.

Điều kiện liên thông chỉ xét những đỉnh có cạnh; một đỉnh không có cạnh nào thì không ảnh hưởng gì.

Đồ thị có hướng làm tương tự, với bậc vào (số cung đi vào) và bậc ra (số cung đi ra). Có chu trình Euler khi mọi đỉnh có bậc vào bằng bậc ra; có đường đi Euler từ $s$ tới $t$ khi đỉnh $s$ có bậc ra hơn bậc vào đúng $1$, đỉnh $t$ có bậc vào hơn bậc ra đúng $1$, còn mọi đỉnh khác có bậc vào bằng bậc ra. Cả hai trường hợp đều cần các cung nằm trong cùng một thành phần liên thông khi bỏ hướng.

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

Đề. Có nhiều đồ thị vô hướng, kết thúc bằng một dòng chỉ có số $0$. Mỗi đồ thị có $n \le 999$ đỉnh. In $1$ nếu đồ thị có chu trình Euler và cả $n$ đỉnh liên thông, ngược lại in $0$.

Lời giải. Ta kiểm hai điều: mọi đỉnh có bậc chẵn, và cả $n$ đỉnh nằm trong một thành phần liên thông. Đề đòi cả $n$ đỉnh liên thông, nên khác với điều kiện chung ở trên, một đỉnh không có cạnh cũng làm đáp án thành $0$. Để kiểm liên thông, ta dùng DSU (bài 2.4): mỗi cạnh hợp hai đầu mút, và mỗi lần hợp được hai tập khác nhau thì số thành phần giảm $1$. Mỗi đồ thị cần đặt lại DSU và bậc của các đỉnh.

#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

Độ phức tạp: $O(n + m)$ cho mỗi đồ thị, tính cả DSU; với $n = 1000$ và $m$ cỡ vài nghìn cạnh, cần khoảng $10^4$ phép tính.

IIDựng chu trình: thuật toán Hierholzer

Giả sử mọi đỉnh có bậc chẵn. Ta bắt đầu từ một đỉnh $s$ và cứ đi theo một cạnh chưa dùng bất kỳ, cho tới khi đứng ở một đỉnh không còn cạnh chưa dùng. Ta có thể thấy rằng chỗ kẹt luôn là chính đỉnh $s$ (xem ô Chứng minh), nên ta được một chu trình. Nếu chu trình này chưa đi hết các cạnh, các cạnh còn lại gắn vào một đỉnh nào đó trên chu trình; từ đỉnh đó ta đi thêm một vòng nhỏ theo các cạnh chưa dùng, rồi chèn vòng nhỏ đó vào chu trình lớn tại đúng đỉnh ấy. Lặp lại cho tới khi hết cạnh, ta được chu trình Euler.

Thuật toán Hierholzer làm việc chèn này một cách tự động bằng một ngăn xếp:

• ban đầu ngăn xếp chỉ có đỉnh $s$;
• xét đỉnh trên cùng của ngăn xếp: nếu nó còn cạnh chưa dùng, đánh dấu cạnh đó đã dùng và đưa đỉnh ở đầu kia vào ngăn xếp;
• nếu nó không còn cạnh chưa dùng, lấy nó ra khỏi ngăn xếp và ghi vào kết quả.

Khi ngăn xếp rỗng, dãy đỉnh trong kết quả là chu trình Euler viết theo thứ tự ngược; đảo lại là xong. Trong mô phỏng dưới đây, cạnh xanh lá là cạnh đã dùng, đỉnh xanh dương là đỉnh đang nằm trên ngăn xếp; bạn có thể thêm một cạnh để thấy điều kiện bậc chẵn bị hỏng:

Khi cài đặt cho đồ thị vô hướng, mỗi cạnh nằm trong danh sách kề của cả hai đầu mút. Đi theo cạnh từ một đầu thì đầu kia cũng phải biết cạnh đó đã dùng, vì vậy danh sách kề lưu số hiệu của cạnh chứ không lưu đỉnh kề, và ta đánh dấu đã dùng theo số hiệu cạnh. Mỗi đỉnh giữ thêm một con trỏ tới cạnh đầu tiên chưa xét trong danh sách kề của nó; con trỏ chỉ tiến, nên cả thuật toán chỉ tốn $O(n + m)$. Dùng ngăn xếp tự quản lý thay cho đệ quy, vì đệ quy sâu tới $m$ tầng có thể tràn bộ nhớ ngăn xếp.

Nếu đồ thị có cạnh nằm ở thành phần không chứa $s$, thuật toán không đi tới được chúng, và kết quả có ít hơn $m + 1$ đỉnh. Vì vậy thay cho bước kiểm liên thông riêng, ta chỉ cần kiểm kết quả có đúng $m + 1$ đỉnh hay không.

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

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

Lời giải. Nếu có đỉnh bậc lẻ thì không có chu trình. Ngược lại, ta chạy Hierholzer từ đỉnh $1$; kết quả có ít hơn $m + 1$ đỉnh nghĩa là có cạnh không tới được từ đỉnh $1$, cũng không có chu trình. Trong code, eu[e] và ev[e] là hai đầu mút của cạnh $e$, g[u] là danh sách số hiệu các cạnh nối với $u$, used[e] đánh dấu cạnh đã dùng, và ptr[u] là con trỏ của đỉnh $u$.

#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

Độ phức tạp: $O(n + m)$, vì mỗi cạnh được xét hai lần (một lần từ mỗi đầu) và mỗi con trỏ chỉ tiến; với $n = 10^5$ và $m = 2 \cdot 10^5$ cần khoảng $5 \cdot 10^5$ phép tính.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e5 + 5;
ll n, m, ptr[N];
vector<ll> g[N];

signed main() {
    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    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]++]);
    }
    reverse(path.begin(), path.end());
    for (ll v : path) cout << v << ' ';
    cout << '\n';
}

ChạyInput3 3
1 2
2 3
3 1

Output1 2 1 3 2 3 1

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á:

Lưu danh sách kề bằng mảng liên kết (ba mảng head, nxt, to) nhanh hơn vector khoảng $3{,}8$ lần, vì không phải cấp phát bộ nhớ riêng cho từng đỉnh. Với đồ thị cỡ triệu cạnh mà thời gian sát giới hạn, nên cân nhắc đổi sang cách này.

IIIĐường đi Euler trên đồ thị có hướng

Trên đồ thị có hướng, mỗi cung chỉ nằm trong danh sách kề của đỉnh xuất phát, nên không cần đánh dấu cung đã dùng: con trỏ của mỗi đỉnh là đủ. Hierholzer giữ nguyên các bước còn lại. Nếu cần đường đi thay vì chu trình, ta bắt đầu từ đỉnh có bậc ra hơn bậc vào đúng $1$; đường đi sẽ tự kết thúc ở đỉnh có bậc vào hơn bậc ra.

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

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

Lời giải. Đường đi Euler từ $1$ tới $n$ cần đỉnh $1$ có bậc ra hơn bậc vào đúng $1$, đỉnh $n$ có bậc vào hơn bậc ra đúng $1$, và mọi đỉnh khác cân bằng. Nếu đúng như vậy, ta chạy Hierholzer từ đỉnh $1$; kết quả thiếu cung nghĩa là có cung không tới được, cũng in IMPOSSIBLE. Ở đây g[u] lưu thẳng đỉnh đích của các cung đi ra từ $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

Độ phức tạp: $O(n + m)$; với $n = 10^5$ và $m = 2 \cdot 10^5$ cần khoảng $4 \cdot 10^5$ phép tính.

Sử dụng kiến thức này cũng có thể giải bài: tìm đường đi Euler có dãy đỉnh nhỏ nhất theo thứ tự từ điển. Sắp xếp danh sách kề của mỗi đỉnh tăng dần, rồi chạy Hierholzer từ đỉnh có bậc ra hơn bậc vào (nếu có), hoặc từ đỉnh nhỏ nhất có cung ra; thuật toán luôn đi theo cung nhỏ nhất còn lại trước, và vòng nào quay về sớm được ghi vào sau, đúng vị trí của nó.

IVĐịnh hướng cạnh để các đỉnh cân bằng

Bài toán: cho đồ thị vô hướng, hãy định hướng mỗi cạnh (chọn một trong hai chiều) sao cho có nhiều đỉnh cân bằng nhất, tức là có bậc vào bằng bậc ra.

Một đỉnh có bậc lẻ không bao giờ cân bằng được, vì bậc vào cộng bậc ra của nó là số lẻ. Ta sẽ thấy mọi đỉnh bậc chẵn đều cân bằng được cùng lúc. Nếu mọi đỉnh có bậc chẵn, ta đi theo các chu trình Euler (mỗi thành phần liên thông một chu trình) và định hướng mỗi cạnh theo chiều đi qua nó: mỗi lần đi qua một đỉnh dùng một cạnh vào và một cạnh ra, nên mọi đỉnh đều cân bằng.

Khi có đỉnh bậc lẻ, ta thêm một đỉnh phụ và nối nó với mọi đỉnh bậc lẻ bằng một cạnh tạm. Số đỉnh bậc lẻ luôn chẵn, vì tổng các bậc bằng hai lần số cạnh, nên sau khi thêm, mọi đỉnh kể cả đỉnh phụ đều có bậc chẵn. Định hướng theo chu trình Euler như trên rồi bỏ các cạnh tạm: mỗi đỉnh bậc chẵn ban đầu không có cạnh tạm nào nên vẫn cân bằng.

Khi cài đặt, ta không cần ghi lại cả chu trình. Hierholzer đi theo mỗi cạnh đúng một lần; định hướng mỗi cạnh theo đúng chiều đi qua nó lúc đó là đủ, vì theo ô Chứng minh ở mục trước, mỗi vòng đi đều quay về chính chỗ nó bắt đầu.

Ví dụCải Cách Đường Một Chiều

Đề. Có nhiều bộ dữ liệu. Mỗi bộ là một đồ thị vô hướng $n \le 200$ đỉnh, không có khuyên hay cạnh song song, có thể không liên thông; tổng $n$ qua các bộ không quá $200$. Định hướng mọi cạnh để có nhiều đỉnh cân bằng nhất. In số đỉnh cân bằng, rồi in các cạnh đã định hướng theo thứ tự bất kỳ.

Lời giải. Theo lập luận trên, đáp án là số đỉnh có bậc chẵn. Đỉnh phụ là đỉnh $0$; các cạnh tạm được đánh số sau $m$ cạnh thật, nên khi đi qua một cạnh, chỉ cần in nó nếu số hiệu không quá $m$. Đồ thị có thể không liên thông, nên ta bắt đầu Hierholzer từ mọi đỉnh còn cạnh chưa dùng.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 205, M = 20505;
ll t, 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 >> t;
    while (t--) {
        cin >> n >> m;
        for (ll u = 0; u <= n; u++) g[u].clear(), ptr[u] = 0;
        for (ll i = 1; i <= m; i++) {
            cin >> eu[i] >> ev[i];
            g[eu[i]].push_back(i);
            g[ev[i]].push_back(i);
        }
        ll k = m, ans = 0;
        for (ll u = 1; u <= n; u++) {
            if (g[u].size() % 2 == 0) {
                ans++;
                continue;
            }
            k++;
            eu[k] = 0, ev[k] = u;
            g[0].push_back(k);
            g[u].push_back(k);
        }
        for (ll i = 1; i <= k; i++) used[i] = 0;
        cout << ans << '\n';
        for (ll s = 0; s <= n; s++) {
            vector<ll> st = {s};
            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()) st.pop_back();
                else {
                    ll e = g[u][ptr[u]], v = eu[e] == u ? ev[e] : eu[e];
                    used[e] = 1;
                    if (e <= m) cout << u << ' ' << v << '\n';
                    st.push_back(v);
                }
            }
        }
    }
}

ChạyInput1
4 3
1 2
2 3
3 4

Output2
1 2
2 3
3 4

Độ phức tạp: $O(n + m)$ cho mỗi bộ dữ liệu; với $n = 200$ và $m \approx 2 \cdot 10^4$ cạnh cần khoảng $10^5$ phép tính.

VXâu de Bruijn

Bài toán: với số nguyên $n$, tìm xâu nhị phân ngắn nhất chứa mọi xâu nhị phân dài $n$ (mỗi xâu như vậy gọi là một mẫu). Chẳng hạn với $n = 2$, xâu $00110$ chứa đủ bốn mẫu $00$, $01$, $11$, $10$.

Một xâu dài $L$ có đúng $L - n + 1$ đoạn con dài $n$, mà cần đủ $2^n$ mẫu khác nhau, nên $L \ge 2^n + n - 1$. Ta sẽ dựng được xâu đúng độ dài này bằng chu trình Euler.

Dựng đồ thị de Bruijn: mỗi đỉnh là một xâu nhị phân dài $n - 1$, và mỗi mẫu $n$ bit là một cung, đi từ đỉnh là $n - 1$ bit đầu của mẫu tới đỉnh là $n - 1$ bit cuối của mẫu. Mỗi đỉnh có đúng $2$ cung ra (thêm bit $0$ hoặc bit $1$ vào cuối) và đúng $2$ cung vào, và từ một đỉnh bất kỳ đi tới được mọi đỉnh khác bằng cách lần lượt thêm các bit của đỉnh đích. Vì vậy đồ thị có chu trình Euler qua cả $2^n$ cung. Đi theo chu trình đó: viết $n - 1$ bit của đỉnh xuất phát, rồi mỗi lần đi qua một cung thì viết thêm bit cuối của mẫu ứng với cung đó. Mỗi đoạn con dài $n$ của xâu thu được là một cung của chu trình, tức là một mẫu, và mỗi mẫu xuất hiện đúng một lần. Xâu dài đúng $2^n + n - 1$.

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. Đỉnh là số nguyên có $n - 1$ bit; cung từ $u$ theo bit $b$ đi tới $(2u + b) \bmod 2^{n-1}$, tức là đẩy bit $b$ vào cuối rồi bỏ bit đầu. Mỗi đỉnh có đúng hai cung ra, nên con trỏ của mỗi đỉnh chỉ cần đếm $0$, $1$ hoặc $2$ cung đã dùng, thử bit $0$ trước. Mỗi phần tử của ngăn xếp nhớ thêm bit của cung đã đưa nó vào; khi lấy một phần tử ra, ta ghi bit đó (đỉnh xuất phát có bit $-1$, không ghi). Đảo dãy bit đã ghi, ta được bit cuối của các cung theo thứ tự đi, và đặt nó sau $n - 1$ bit $0$ của đỉnh xuất phát. Khi $n = 1$, đồ thị có một đỉnh với hai khuyên, cách làm vẫn đúng.

#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

Độ phức tạp: $O(2^n)$; với $n = 15$ cần khoảng $6 \cdot 10^4$ bước, và xâu dài $2^n + n - 1$.

Sử dụng kiến thức này cũng có thể giải bài: khôi phục một dãy khi chỉ biết các cặp phần tử kề nhau của nó, đã bị xáo trộn. Mỗi cặp là một cạnh nối hai giá trị, nên dãy chính là một đường đi Euler trên đồ thị các giá trị (nén giá trị trước khi dựng đồ thị).