Sắp xếp tô-pô

Mức độ: Nâng cao

Có n môn học, một số môn phải học sau môn khác (học Tin học 2 sau Tin học 1). Xếp thứ tự học sao cho mọi môn đều học sau các môn cần học trước. Vẽ mỗi môn là một đỉnh, mỗi ràng buộc “u trước v” là một cạnh có hướng u → v. Thứ tự cần tìm gọi là thứ tự tô-pô: mọi cạnh đều đi từ trước ra sau.

Thứ tự tô-pô có khi và chỉ khi đồ thị không có chu trình (gọi là DAG). Có chu trình 1 → 2 → 3 → 1 thì môn nào trong ba môn cũng phải học trước chính nó, vô lý.

Thuật toán Kahn

Bậc vào của đỉnh v là số cạnh đi vào v (số môn phải học trước v). Đỉnh có bậc vào 0 thì học ngay được.

1. Đưa mọi đỉnh có bậc vào 0 vào hàng đợi.
2. Lấy một đỉnh u ra, ghi vào thứ tự. Với mỗi cạnh u → v, giảm bậc vào của v đi 1 (đã học xong một môn cần trước v); bậc vào của v về 0 thì đưa v vào hàng đợi.
3. Lặp đến khi hàng đợi rỗng.

Nếu cuối cùng ghi được đủ n đỉnh thì có thứ tự tô-pô. Còn thiếu thì các đỉnh thiếu nằm trên (hoặc phía sau) một chu trình: bậc vào của chúng không bao giờ về 0.

Đồ thị 1 → 2, 1 → 3, 2 → 4, 3 → 4:

Bước	Lấy ra	Bậc vào sau bước (đỉnh 1 2 3 4)	Hàng đợi
đầu		0 1 1 2	1
1	1	- 0 0 2	2 3
2	2	- - 0 1	3
3	3	- - - 0	4
4	4

Thứ tự 1 2 3 4.

Python

import sys
from collections import deque
du_lieu = sys.stdin.read().split()
n, m = int(du_lieu[0]), int(du_lieu[1])
ke = [[] for _ in range(n + 1)]
bac_vao = [0] * (n + 1)
for i in range(m):
    u, v = int(du_lieu[2 + 2 * i]), int(du_lieu[3 + 2 * i])
    ke[u].append(v)
    bac_vao[v] += 1
hang_doi = deque(u for u in range(1, n + 1) if bac_vao[u] == 0)
thu_tu = []
while hang_doi:
    u = hang_doi.popleft()
    thu_tu.append(u)
    for v in ke[u]:
        bac_vao[v] -= 1
        if bac_vao[v] == 0:
            hang_doi.append(v)
print(*thu_tu if len(thu_tu) == n else ["IMPOSSIBLE"])

C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> ke(n + 1);
    vector<int> bacVao(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        ke[u].push_back(v);
        bacVao[v]++;
    }
    queue<int> hangDoi;
    for (int u = 1; u <= n; u++)
        if (bacVao[u] == 0) hangDoi.push(u);
    vector<int> thuTu;
    while (!hangDoi.empty()) {
        int u = hangDoi.front();
        hangDoi.pop();
        thuTu.push_back(u);
        for (int v : ke[u])
            if (--bacVao[v] == 0) hangDoi.push(v);
    }
    if ((int)thuTu.size() < n) cout << "IMPOSSIBLE\n";
    else
        for (int i = 0; i < n; i++) cout << thuTu[i] << (i + 1 < n ? ' ' : '\n');
    return 0;
}

Mỗi đỉnh vào hàng đợi một lần, mỗi cạnh được xét một lần: cả bài n + m bước.

Thứ tự tô-pô nhỏ nhất

Thường có nhiều thứ tự tô-pô (ở ví dụ trên, 1 3 2 4 cũng đúng). Đề hay yêu cầu thứ tự nhỏ nhất theo từ điển: thay hàng đợi bằng hàng đợi ưu tiên, mỗi bước lấy đỉnh số nhỏ nhất trong các đỉnh đang có bậc vào 0. Mỗi lần lấy, thêm mất khoảng log₂n bước.

Quy hoạch động trên DAG

Thứ tự tô-pô là thứ tự tính tự nhiên cho quy hoạch động trên đồ thị có hướng: đi theo thứ tự đó thì khi tới v, mọi đỉnh có cạnh vào v đã được tính xong.

Câu hỏi	Công thức theo thứ tự tô-pô
đường đi dài nhất kết thúc tại v	dai[v] = max(dai[u] + 1) qua các cạnh u → v
số đường đi từ s tới v	so[v] = tổng so[u] qua các cạnh u → v, so[s] = 1
thời gian sớm nhất hoàn thành việc v	xong[v] = tv + max(xong[u]) qua các việc u phải làm trước v

Đường đi dài nhất trên đồ thị có chu trình là bài rất khó, nhưng trên DAG chỉ cần n + m bước.

Luyện tập

Gồm 15 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Thứ tự tô-pô

Bài 1. Kiểm tra một thứ tự

Đồ thị có hướng n đỉnh, m cạnh. Dòng đầu có n, m (1 ≤ n ≤ 2 × 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v (cạnh u → v), dòng cuối là một hoán vị của 1, …, n. In ra YES nếu hoán vị đó là một thứ tự tô-pô (mọi cạnh đi từ đỉnh đứng trước tới đỉnh đứng sau), ngược lại NO.

Ví dụ:

Nhập	In ra
4 4 1 2 1 3 2 4 3 4 1 3 2 4	YES

Kiểm tra: nhập

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

Xem đáp số

YES

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Có chu trình không

Đồ thị có hướng n đỉnh, m cạnh. Dòng đầu có n, m (1 ≤ n ≤ 2 × 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v (cạnh u → v, có thể u = v). In ra YES nếu đồ thị có chu trình, ngược lại NO.

Ví dụ:

Nhập	In ra
4 4 1 2 2 3 3 1 3 4	YES

Kiểm tra: nhập

6 7
1 2
2 3
3 4
1 5
5 6
6 3
4 6

Xem đáp số

YES

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Thứ tự học nhỏ nhất

Có n môn học và m ràng buộc u v: môn u phải học trước môn v. Dòng đầu có n, m (1 ≤ n ≤ 2 × 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau là các ràng buộc. In ra thứ tự học thỏa mọi ràng buộc, nhỏ nhất theo thứ tự từ điển; nếu không có thì in IMPOSSIBLE.

Ví dụ:

Nhập	In ra
5 4 2 1 3 1 4 2 5 3	4 2 5 3 1

Kiểm tra: nhập

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

Xem đáp số

3 4 6 2 5 1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Thứ tự có duy nhất không

Đồ thị có hướng n đỉnh, m cạnh, không có chu trình. Dòng đầu có n, m (1 ≤ n ≤ 2 × 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau là các cạnh. In ra YES nếu đồ thị chỉ có đúng một thứ tự tô-pô, ngược lại NO.

Ví dụ:

Nhập	In ra
3 3 1 2 2 3 1 3	YES

Kiểm tra: nhập

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

Xem đáp số

NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Lập lịch

Bài 5. Số học kỳ ít nhất

Có n môn học và m ràng buộc u v (học u xong mới được học v), không có chu trình. Mỗi học kỳ học được bao nhiêu môn cũng được, miễn là các môn cần trước đã học ở các kỳ trước. Dòng đầu có n, m (1 ≤ n ≤ 2 × 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau là các ràng buộc. In ra số học kỳ ít nhất để học hết.

Ví dụ:

Nhập	In ra
5 4 1 2 2 3 1 4 4 5	3

Kiểm tra: nhập

8 9
1 2
2 3
3 4
5 6
6 4
7 8
8 4
2 6
6 8

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 6. Thời gian hoàn thành dự án

Dự án có n việc, việc i mất t_i ngày. Có m ràng buộc u v: việc v chỉ bắt đầu khi việc u xong. Các việc không ràng buộc nhau làm song song được (nhân lực không giới hạn), không có chu trình. Dòng đầu có n, m (1 ≤ n ≤ 2 × 10⁵, 0 ≤ m ≤ 2 × 10⁵), dòng thứ hai có n số t_i (1 ≤ t_i ≤ 10⁹), m dòng sau là các ràng buộc. In ra số ngày ít nhất để xong cả dự án.

Ví dụ:

Nhập	In ra
4 3 3 2 4 1 1 2 1 3 2 4	7

Kiểm tra: nhập

6 7
2 4 3 5 1 6
1 2
1 3
2 4
3 4
4 5
3 6
6 5

Xem đáp số

12

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Việc găng

Như bài 6. Một việc là việc găng nếu chỉ cần việc đó chậm thêm 1 ngày là cả dự án xong muộn hơn. Dòng đầu có n, m, dòng thứ hai có n số t_i, m dòng sau là các ràng buộc. In ra các việc găng theo thứ tự số tăng dần.

Ví dụ:

Nhập	In ra
4 3 3 2 4 1 1 2 1 3 2 4	1 3

Kiểm tra: nhập

6 7
2 4 3 5 1 6
1 2
1 3
2 4
3 4
4 5
3 6
6 5

Xem đáp số

1 2 3 4 5 6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Quy hoạch động trên DAG

Bài 8. Đường đi dài nhất

Đồ thị có hướng không chu trình n đỉnh, m cạnh. Dòng đầu có n, m (2 ≤ n ≤ 2 × 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau là các cạnh. In ra số cạnh nhiều nhất trên một đường đi từ đỉnh 1 tới đỉnh n, hoặc -1 nếu không có đường đi.

Ví dụ:

Nhập	In ra
5 6 1 2 2 3 3 5 1 4 4 5 2 4	3

Kiểm tra: nhập

7 9
1 2
1 3
2 4
3 4
4 5
5 7
3 6
6 7
2 6

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Đếm số đường đi

Đồ thị có hướng không chu trình n đỉnh, m cạnh (có thể có nhiều cạnh nối cùng hai đỉnh, mỗi cạnh tính riêng). Dòng đầu có n, m (2 ≤ n ≤ 2 × 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau là các cạnh. In ra số đường đi khác nhau từ đỉnh 1 tới đỉnh n, chia lấy dư 10⁹ + 7.

Ví dụ:

Nhập	In ra
4 5 1 2 1 3 2 4 3 4 2 3	3

Kiểm tra: nhập

6 9
1 2
1 3
2 3
2 4
3 4
3 5
4 6
5 6
4 5

Xem đáp số

8

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Đường đi giá trị lớn nhất

Đồ thị có hướng không chu trình n đỉnh, m cạnh, mỗi cạnh có giá trị w (có thể âm). Dòng đầu có n, m (2 ≤ n ≤ 2 × 10⁵, 0 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v, w (|w| ≤ 10⁹). In ra tổng giá trị lớn nhất của một đường đi từ đỉnh 1 tới đỉnh n, hoặc -1000000000000000000 nếu không có đường đi.

Ví dụ:

Nhập	In ra
4 5 1 2 3 1 3 -1 2 4 2 3 4 10 2 3 1	14

Kiểm tra: nhập

6 8
1 2 5
1 3 -2
2 4 -7
3 4 4
2 5 1
4 6 3
5 6 -1
3 5 6

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. Đi trên lưới có ô cấm

Bảng h hàng, w cột gồm . và # (ô cấm). Đi từ ô trên cùng bên trái tới ô dưới cùng bên phải, mỗi bước chỉ sang phải hoặc xuống, không vào ô cấm. Dòng đầu có h, w (1 ≤ h, w ≤ 1000), h dòng sau là bảng. In ra số cách đi, chia lấy dư 10⁹ + 7.

Ví dụ:

Nhập	In ra
3 3 ... .#. ...	2

Kiểm tra: nhập

5 6
......
..#...
.#..#.
...#..
#.....

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Đường tăng dài nhất trên bảng

Bảng h hàng, w cột, mỗi ô ghi một số. Từ một ô được đi sang ô chung cạnh có số lớn hơn hẳn. Dòng đầu có h, w (1 ≤ h, w ≤ 500), h dòng sau mỗi dòng có w số (|giá trị| ≤ 10⁹). In ra số ô nhiều nhất trên một đường đi như vậy.

Ví dụ:

Nhập	In ra
3 3 9 9 4 6 6 8 2 1 1	4

Kiểm tra: nhập

4 5
3 4 5 1 2
2 7 6 9 3
1 8 3 4 4
5 6 7 1 2

Xem đáp số

8

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Vận dụng

Bài 13. Bảng chữ cái lạ

Một ngôn ngữ dùng các chữ cái thường tiếng Anh nhưng theo thứ tự khác. Cho n từ đã được xếp theo thứ tự từ điển của ngôn ngữ đó. Dòng đầu có n (1 ≤ n ≤ 1000), n dòng sau mỗi dòng là một từ (dài từ 1 đến 100). In ra một thứ tự của các chữ cái xuất hiện trong các từ phù hợp với danh sách, chọn thứ tự nhỏ nhất theo bảng chữ cái thường khi có nhiều lựa chọn; nếu danh sách mâu thuẫn thì in IMPOSSIBLE.

Ví dụ:

Nhập	In ra
5 wrt wrf er ett rftt	wertf

Kiểm tra: nhập

6
bca
baa
ac
acb
cb
cbd

Xem đáp số

IMPOSSIBLE

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 14. Định hướng các cạnh

Đồ thị có n đỉnh và m cạnh, mỗi cạnh có loại 1 u v (cạnh có hướng u → v, đã cố định) hoặc 0 u v (cạnh vô hướng, chưa chọn hướng). Dòng đầu có n, m (1 ≤ n ≤ 2 × 10⁵, 1 ≤ m ≤ 2 × 10⁵), m dòng sau là các cạnh (u khác v). Cần chọn hướng cho mọi cạnh vô hướng để đồ thị không có chu trình. Nếu không được, in NO. Nếu được, in YES rồi in m dòng, mỗi dòng là một cạnh a b (theo đúng thứ tự đề cho) đã chọn hướng a → b; cạnh vô hướng được hướng từ đỉnh đứng trước tới đỉnh đứng sau trong thứ tự tô-pô nhỏ nhất theo từ điển của các cạnh có hướng.

Ví dụ:

Nhập	In ra
4 4 1 1 2 0 2 3 1 4 3 0 1 4	YES 1 2 2 3 4 3 1 4

Kiểm tra: nhập

5 6
0 1 2
1 3 2
0 3 4
1 4 5
0 5 1
1 1 3

Xem đáp số

YES
1 2
3 2
3 4
4 5
1 5
1 3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Mỗi đỉnh đi tới được bao nhiêu đỉnh

Đồ thị có hướng không chu trình n đỉnh, m cạnh. Dòng đầu có n, m (1 ≤ n ≤ 5 × 10⁴, 0 ≤ m ≤ 10⁵), m dòng sau là các cạnh. Với mỗi đỉnh u, in ra số đỉnh đi tới được từ u (tính cả u).

Ví dụ:

Nhập	In ra
5 5 1 2 1 3 2 4 3 4 4 5	5 3 3 2 1

Kiểm tra: nhập

8 9
1 2
2 3
1 4
4 3
3 5
6 7
7 8
6 8
8 5

Xem đáp số

5 3 2 3 1 4 3 2

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.