Topological Sort

Kahn

Bậc vào của một đỉnh là số cung đi vào nó. Đỉnh có bậc vào bằng 0 không phải chờ ai, có thể đứng đầu hàng.

Thuật toán Kahn lặp: lấy một đỉnh bậc vào 0, đưa vào thứ tự, gỡ mọi cung đi ra từ nó (giảm bậc vào của các đỉnh đích). Đỉnh nào về bậc 0 thì đẩy vào hàng đợi. Mỗi đỉnh và mỗi cung được xử lý một lần, $O(n + m)$.

Nếu kết thúc mà thứ tự có ít hơn $n$ đỉnh, mỗi đỉnh còn lại có một đỉnh đi tới nó cũng còn lại. Lần ngược mãi thì phải lặp lại một đỉnh, tức đồ thị có chu trình. Ngược lại, DAG luôn có ít nhất một đỉnh bậc vào 0 (đỉnh đầu của một đường dài nhất), nên Kahn không kẹt khi không có chu trình.

Cách thứ hai dùng DFS: một đỉnh xong (đã duyệt hết các đỉnh đi ra) sau mọi đỉnh nó đi tới, nên đảo ngược thứ tự xong là một thứ tự tô pô. Tìm chu trình bằng DFS cần ba trạng thái: chưa thăm, đang trên ngăn xếp đệ quy, đã xong; gặp cung tới đỉnh đang trên ngăn xếp là có chu trình.

Ví dụLịch Trình Tiên Quyết

Đề. $n \le 10^5$ chuyên đề, $m \le 2 \cdot 10^5$ ràng buộc $a$ trước $b$. In một thứ tự hợp lệ, hoặc IMPOSSIBLE.

Lời giải. Thuật toán Kahn: deg[v] là số cung đi vào $v$ chưa bị gỡ; đỉnh có deg = 0 không còn điều kiện nào phải chờ, xếp tiếp được. Đỉnh nằm trên một chu trình (hay phía sau chu trình) không bao giờ về 0, nên thứ tự thu được thiếu đỉnh nghĩa là có chu trình.

Bước 1: đếm bậc vào.

for (ll i = 1; i <= m; i++) {
    ll a, b;
    cin >> a >> b;
    g[a].push_back(b);
    deg[b]++;
}

Bước 2: lấy dần các đỉnh sẵn sàng. Mọi đỉnh bậc vào 0 vào hàng đợi trước. Lấy $u$ ra thì gỡ mọi cung $u \to v$; đỉnh nào về 0 thì vào hàng đợi.

queue<ll> q;
for (ll u = 1; u <= n; u++)
    if (!deg[u]) q.push(u);
vector<ll> ord;
while (!q.empty()) {
    ll u = q.front();
    q.pop();
    ord.push_back(u);
    for (ll v : g[u])
        if (--deg[v] == 0) q.push(v);
}

Bước 3: kiểm chu trình. ord có đủ $n$ đỉnh thì in, không thì in IMPOSSIBLE.

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

const ll N = 1e5 + 5;
ll n, m, deg[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 a, b;
        cin >> a >> b;
        g[a].push_back(b);
        deg[b]++;
    }
    queue<ll> q;
    for (ll u = 1; u <= n; u++)
        if (!deg[u]) q.push(u);
    vector<ll> ord;
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        ord.push_back(u);
        for (ll v : g[u])
            if (--deg[v] == 0) q.push(v);
    }
    if ((ll)ord.size() < n) {
        cout << "IMPOSSIBLE\n";
        return 0;
    }
    for (ll u : ord) cout << u << ' ';
    cout << '\n';
}

ChạyInput6 5
3 1
5 2
1 4
2 4
4 6

Output3 5 1 2 4 6

Độ phức tạp: mỗi đỉnh và mỗi cung được xử lý một lần: $O(n + m)$.

Nhỏ nhất, duy nhất

Kahn được tự do chọn đỉnh nào trong số các đỉnh bậc vào 0. Thay hàng đợi bằng hàng đợi ưu tiên lấy đỉnh nhỏ nhất thì được thứ tự tô pô nhỏ nhất theo từ điển: ở mỗi vị trí, đỉnh được chọn là đỉnh nhỏ nhất có thể đứng ở đó, và chọn nó không làm mất lựa chọn nào về sau. Chi phí thành $O((n + m) \log n)$.

Cùng lý lẽ đó, thứ tự tô pô là duy nhất khi và chỉ khi mỗi bước chỉ có đúng một đỉnh bậc vào 0. Nếu có lúc hai đỉnh cùng sẵn sàng thì đổi chỗ chúng vẫn hợp lệ, vì không cung nào nối hai đỉnh đó (một cung sẽ làm một trong hai còn bậc vào dương). Cũng vậy, thứ tự duy nhất là thứ tự mà mọi cặp đỉnh liên tiếp có cung nối nhau.

Ví dụDãy Lệnh Ưu Tiên

Đề. $n \le 2 \cdot 10^5$ lệnh, $m \le 2 \cdot 10^5$ ràng buộc (có thể trùng). In thứ tự thực hiện nhỏ nhất theo từ điển, hoặc $-1$ nếu không có.

Lời giải. Kahn như ví dụ trước, khác đúng một chỗ: trong các đỉnh đang sẵn sàng, luôn lấy đỉnh có số hiệu nhỏ nhất. Vì sao ra thứ tự nhỏ nhất theo từ điển: ở mỗi vị trí, đỉnh đặt được phải là đỉnh đang có bậc vào 0, và chọn đỉnh nhỏ nhất không làm đỉnh nào khác mất khả năng được đặt sau (nó chỉ gỡ thêm cung). Ràng buộc trùng làm deg[v] tăng hai lần và cũng bị gỡ hai lần, nên không cần lọc.

Bước 1: hàng đợi ưu tiên lấy số nhỏ nhất. priority_queue với greater thay cho queue.

priority_queue<ll, vector<ll>, greater<ll>> pq;
for (ll u = 1; u <= n; u++)
    if (!deg[u]) pq.push(u);
vector<ll> ord;
while (!pq.empty()) {
    ll u = pq.top();
    pq.pop();
    ord.push_back(u);
    for (ll v : g[u])
        if (--deg[v] == 0) pq.push(v);
}

Bước 2: kiểm chu trình như ví dụ trước, không đủ $n$ đỉnh thì in $-1$.

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

const ll N = 2e5 + 5;
ll n, m, deg[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 a, b;
        cin >> a >> b;
        g[a].push_back(b);
        deg[b]++;
    }
    priority_queue<ll, vector<ll>, greater<ll>> pq;
    for (ll u = 1; u <= n; u++)
        if (!deg[u]) pq.push(u);
    vector<ll> ord;
    while (!pq.empty()) {
        ll u = pq.top();
        pq.pop();
        ord.push_back(u);
        for (ll v : g[u])
            if (--deg[v] == 0) pq.push(v);
    }
    if ((ll)ord.size() < n) {
        cout << -1 << '\n';
        return 0;
    }
    for (ll u : ord) cout << u << ' ';
    cout << '\n';
}

ChạyInput6 6
3 1
3 5
2 5
1 4
5 4
4 6

Output2 3 1 5 4 6

Độ phức tạp: $O((n + m) \log n)$ vì hàng đợi ưu tiên.

Cái giá của thứ tự nhỏ nhất không lớn:

priority_queue chậm hơn queue khoảng 1,3 lần trên đồ thị ngẫu nhiên. Đề đòi thứ tự nhỏ nhất thì cứ dùng, không cần lo thời gian.

Quy hoạch động

Trên DAG, $\mathrm{dp}[v]$ phụ thuộc vào các đỉnh đi tới $v$ (hay các đỉnh $v$ đi tới) không bao giờ tạo vòng phụ thuộc. Xử lý đỉnh theo thứ tự tô pô, mỗi khi lấy $u$ ra thì đẩy giá trị sang mọi $v$ mà $u \to v$: tới lượt $v$, mọi đóng góp đã đủ. Đường dài nhất là $\mathrm{dp}[v] = \max(\mathrm{dp}[u] + 1)$, số đường từ nguồn là $\mathrm{dp}[v] = \sum \mathrm{dp}[u]$. Trên đồ thị tổng quát, đường dài nhất là bài khó; DAG làm nó thành $O(n + m)$.

Có thể lồng thẳng việc đẩy giá trị vào vòng lặp Kahn, không cần lưu thứ tự riêng.

Ví dụHành Trình Qua Các Mốc

Đề. DAG $n \le 10^5$ đỉnh, $m \le 10^5$ cung. Tìm số cung lớn nhất của một đường đi có hướng.

Lời giải. $\mathrm{dp}[v]$ là số cung của đường dài nhất kết thúc ở $v$, ban đầu 0 vì đường bắt đầu ở đâu cũng được. Đi theo thứ tự tô pô: lúc $v$ vào hàng đợi, mọi cung vào $v$ đã bị gỡ, tức mọi đỉnh đi trước $v$ đã xong, nên $\mathrm{dp}[v]$ đã là giá trị cuối cùng.

Bước 1: cập nhật khi gỡ cung. Mỗi khi gỡ cung $u \to v$, thử kéo dài đường tốt nhất tới $u$ thêm một cung.

while (!q.empty()) {
    ll u = q.front();
    q.pop();
    ans = max(ans, dp[u]);
    for (ll v : g[u]) {
        dp[v] = max(dp[v], dp[u] + 1);
        if (--deg[v] == 0) q.push(v);
    }
}

ans lấy max lúc lấy đỉnh ra, khi dp[u] chắc chắn đã đủ.

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

const ll N = 1e5 + 5;
ll n, m, deg[N], dp[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);
        deg[v]++;
    }
    queue<ll> q;
    for (ll u = 1; u <= n; u++)
        if (!deg[u]) q.push(u);
    ll ans = 0;
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        ans = max(ans, dp[u]);
        for (ll v : g[u]) {
            dp[v] = max(dp[v], dp[u] + 1);
            if (--deg[v] == 0) q.push(v);
        }
    }
    cout << ans << '\n';
}

ChạyInput6 5
1 3
2 3
3 4
3 5
5 6

Output3

Độ phức tạp: $O(n + m)$.

Ví dụNhững Tuyến Đường Qua Cổng Dịch Chuyển

Đề. DAG $n \le 10^5$ đỉnh, $m \le 2 \cdot 10^5$ cung (có thể trùng, mỗi cung tính riêng). Đếm số đường từ 1 tới $n$ theo modulo $10^9 + 7$.

Lời giải. $\mathrm{dp}[v]$ là số đường từ 1 tới $v$: $\mathrm{dp}[1] = 1$, còn lại 0, và mỗi cung $u \to v$ cộng $\mathrm{dp}[u]$ vào $\mathrm{dp}[v]$ theo thứ tự tô pô. Cung trùng tự được cộng hai lần, đúng ý đề.

Bước 1: Kahn trên cả đồ thị. Hàng đợi bắt đầu từ mọi đỉnh bậc vào 0, không chỉ đỉnh 1. Một đỉnh không tới được từ 1 vẫn có cung đi vào các đỉnh khác và phải được xử lý để gỡ cung đó; bắt đầu chỉ từ 1 thì những đỉnh phía sau nó giữ deg > 0 mãi. Các đỉnh không tới được từ 1 có dp = 0, đẩy đi chỉ cộng 0.

queue<ll> q;
for (ll u = 1; u <= n; u++)
    if (!deg[u]) q.push(u);
dp[1] = 1;

Bước 2: cộng theo cung.

while (!q.empty()) {
    ll u = q.front();
    q.pop();
    for (ll v : g[u]) {
        dp[v] = (dp[v] + dp[u]) % MOD;
        if (--deg[v] == 0) q.push(v);
    }
}

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

const ll N = 1e5 + 5, MOD = 1e9 + 7;
ll n, m, deg[N], dp[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 a, b;
        cin >> a >> b;
        g[a].push_back(b);
        deg[b]++;
    }
    queue<ll> q;
    for (ll u = 1; u <= n; u++)
        if (!deg[u]) q.push(u);
    dp[1] = 1;
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        for (ll v : g[u]) {
            dp[v] = (dp[v] + dp[u]) % MOD;
            if (--deg[v] == 0) q.push(v);
        }
    }
    cout << dp[n] << '\n';
}

ChạyInput5 6
1 2
1 3
2 4
3 4
4 5
2 5

Output3

Độ phức tạp: $O(n + m)$.

Một nguồn, truy vết

Khi đường phải bắt đầu ở một nguồn cố định, các đỉnh không tới được từ nguồn phải bị loại: đặt $\mathrm{dp}$ của chúng là $-\infty$ và chỉ cập nhật từ những đỉnh có giá trị hợp lệ. Vẫn chạy Kahn trên cả đồ thị, hàng đợi bắt đầu từ mọi đỉnh bậc vào 0, như bài đếm đường ở trên.

Lưu par[v] là đỉnh $u$ cho giá trị tốt nhất của $v$, để lần ngược ra đường đi như với BFS (bài 30): lần par từ đích về nguồn rồi đảo lại.

Định hướng cạnh

Một thứ tự tô pô cho mọi đỉnh một vị trí $pos$. Định hướng mọi cạnh từ đỉnh có vị trí nhỏ sang đỉnh có vị trí lớn thì không thể có chu trình, vì đi theo bất kỳ cung nào vị trí cũng tăng. Vậy muốn thêm chiều cho các cạnh vô hướng mà không tạo chu trình, chỉ cần các cung có sẵn đã không có chu trình: lấy một thứ tự tô pô của chúng rồi định hướng phần còn lại theo $pos$.

Ví dụĐịnh Hướng Các Liên Kết

Đề. Nhiều test, tổng $N, M \le 2 \cdot 10^5$. Một số cạnh đã có hướng, số còn lại vô hướng. Định hướng các cạnh vô hướng để cả đồ thị không có chu trình, in YES và mọi cạnh; không được thì in NO.

Lời giải. Nếu các cung đã có hướng tự tạo chu trình thì vô vọng. Ngược lại lấy một thứ tự tô pô của riêng các cung đó, rồi định hướng mọi cạnh vô hướng theo đúng thứ tự ấy, từ vị trí nhỏ sang vị trí lớn. Khi đó mọi cung của kết quả, có sẵn lẫn mới, đều đi từ vị trí nhỏ sang vị trí lớn, nên không thể có chu trình.

Bước 1: chỉ cung có sẵn vào đồ thị. Cạnh vô hướng (et = 0) chờ tới cuối. Nhiều test nên mỗi test xóa g và deg của các đỉnh $1..n$ trước.

for (ll i = 1; i <= m; i++) {
    cin >> et[i] >> ex[i] >> ey[i];
    if (et[i]) {
        g[ex[i]].push_back(ey[i]);
        deg[ey[i]]++;
    }
}

Bước 2: Kahn ghi vị trí. pos[u] là vị trí của $u$ trong thứ tự tô pô. Thiếu đỉnh (k < n) là các cung có sẵn đã có chu trình, in NO.

while (!q.empty()) {
    ll u = q.front();
    q.pop();
    pos[u] = ++k;
    for (ll v : g[u])
        if (--deg[v] == 0) q.push(v);
}

Bước 3: định hướng cạnh vô hướng. In theo chiều pos tăng; cung có sẵn in nguyên.

for (ll i = 1; i <= m; i++) {
    ll x = ex[i], y = ey[i];
    if (!et[i] && pos[x] > pos[y]) swap(x, y);
    cout << x << ' ' << y << '\n';
}

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

const ll N = 2e5 + 5;
ll deg[N], pos[N], et[N], ex[N], ey[N];
vector<ll> g[N];

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

    ll T;
    cin >> T;
    while (T--) {
        ll n, m;
        cin >> n >> m;
        for (ll u = 1; u <= n; u++) {
            g[u].clear();
            deg[u] = 0;
        }
        for (ll i = 1; i <= m; i++) {
            cin >> et[i] >> ex[i] >> ey[i];
            if (et[i]) {
                g[ex[i]].push_back(ey[i]);
                deg[ey[i]]++;
            }
        }
        queue<ll> q;
        for (ll u = 1; u <= n; u++)
            if (!deg[u]) q.push(u);
        ll k = 0;
        while (!q.empty()) {
            ll u = q.front();
            q.pop();
            pos[u] = ++k;
            for (ll v : g[u])
                if (--deg[v] == 0) q.push(v);
        }
        if (k < n) {
            cout << "NO\n";
            continue;
        }
        cout << "YES\n";
        for (ll i = 1; i <= m; i++) {
            ll x = ex[i], y = ey[i];
            if (!et[i] && pos[x] > pos[y]) swap(x, y);
            cout << x << ' ' << y << '\n';
        }
    }
}

ChạyInput1
5 6
1 4 2
0 1 2
1 3 4
0 5 3
0 1 5
1 4 5

OutputYES
4 2
1 2
3 4
3 5
1 5
4 5

Độ phức tạp: mỗi test $O(N + M)$.