Topological Sort

Thuật toán 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, các đỉnh còn lại đều có bậc vào dương trong phần đồ thị còn lại: mỗi đỉnh có một đỉnh đi tới nó cũng còn lại, lần ngược mãi phải lặp, nên đồ 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 bao giờ 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;
using 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';
}

Input6 5
3 1
5 2
1 4
2 4
4 6

Output3 5 1 2 4 6

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

Thứ tự nhỏ nhất và thứ 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. 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). Thứ tự duy nhất cũng 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;
using 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';
}

Input6 6
3 1
3 5
2 5
1 4
5 4
4 6

Output2 3 1 5 4 6

$O((n + m) \log n)$ vì hàng đợi ưu tiên.

Ví dụThứ Hạng Có Duy Nhất

Đề. $n \le 2 \cdot 10^5$ đối tượng, $m$ quan hệ $A_x < A_y$, luôn có ít nhất một cách xếp. Nếu hoán vị thứ hạng $A$ là duy nhất thì in Yes và $A$, không thì No.

Lời giải. Kahn; nếu có lúc hàng đợi chứa từ hai đỉnh trở lên thì đổi thứ tự hai đỉnh đó vẫn hợp lệ, nên thứ hạng không duy nhất. Ngược lại mọi lúc chỉ có đúng một lựa chọn, và đỉnh được lấy ra thứ $k$ có hạng $k$. Đề bảo đảm có ít nhất một cách xếp nên không cần kiểm chu trình.

Bước 1: Kahn có kiểm duy nhất. Kiểm q.size() > 1 mỗi vòng, trước khi lấy.

while (!q.empty()) {
    if (q.size() > 1) {
        cout << "No\n";
        return 0;
    }
    ll u = q.front();
    q.pop();
    rk[u] = ++k;
    for (ll v : g[u])
        if (--deg[v] == 0) q.push(v);
}

Bước 2: in theo số hiệu. Đề đòi hạng của từng đối tượng, nên in rk[1..n], không in thứ tự các đối tượng.

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

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

Input5 4
2 3
3 1
1 5
5 4

OutputYes
3 1 2 5 4

$O(n + m)$.

Quy hoạch động theo thứ tự tô pô

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;
using 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';
}

Input6 5
1 3
2 3
3 4
3 5
5 6

Output3

$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;
using 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';
}

Input5 6
1 2
1 3
2 4
3 4
4 5
2 5

Output3

$O(n + m)$.

Đường dài nhất từ một nguồn và 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ệ. Lưu par[v] là đỉnh $u$ cho giá trị tốt nhất của $v$ để lần ngược đường đi, như với BFS (bài 30).

Ví dụTuyến Bay Qua Nhiều Thành Phố

Đề. DAG $n \le 10^5$ đỉnh, $m \le 2 \cdot 10^5$ cung. In một đường từ 1 tới $n$ đi qua nhiều đỉnh nhất, hoặc IMPOSSIBLE.

Lời giải. Gộp hai ví dụ trước: $\mathrm{dp}[v]$ là số đỉnh nhiều nhất trên một đường từ 1 tới $v$, và par[v] để truy vết như BFS ở bài 30. Đỉnh không tới được từ 1 phải mang giá trị “không hợp lệ” để không kéo theo đỉnh khác.

Bước 1: khởi tạo. dp khởi đầu NEG (không tới được), chỉ dp[1] = 1.

for (ll u = 1; u <= n; u++) dp[u] = NEG;
dp[1] = 1;

Bước 2: Kahn trên cả đồ thị. Như ví dụ đếm đường, hàng đợi bắt đầu từ mọi đỉnh bậc vào 0. Chỉ cập nhật từ đỉnh có dp hợp lệ; mỗi lần dp[v] tăng thì ghi lại par[v].

for (ll v : g[u]) {
    if (dp[u] != NEG && dp[u] + 1 > dp[v]) {
        dp[v] = dp[u] + 1;
        par[v] = u;
    }
    if (--deg[v] == 0) q.push(v);
}

Bước 3: truy vết. $\mathrm{dp}[n]$ vẫn NEG thì in IMPOSSIBLE; không thì lần par từ $n$ về 1 rồi đảo.

vector<ll> path;
for (ll v = n; v != 1; v = par[v]) path.push_back(v);
path.push_back(1);
reverse(path.begin(), path.end());

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

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

Input6 5
1 2
2 6
1 3
3 4
4 6

Output4
1 3 4 6

$O(n + m)$.

Định hướng cạnh theo thứ tự tô pô

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;
using 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';
        }
    }
}

Input1
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

Mỗi test $O(N + M)$.