Bài 35: Sắp xếp topo trong C++ và Python: đồ thị có hướng không chu trình (DAG), thuật toán Kahn, DFS ba màu và quy hoạch động trên DAG
Lời mở đầu
Ở bài 21 em đã biết lưu đồ thị bằng danh sách kề, duyệt BFS và DFS. Hầu hết ví dụ khi đó là đồ thị vô hướng: đường hai chiều, bạn bè quen nhau. Nhưng rất nhiều quan hệ ngoài đời chỉ có một chiều: phải học “Lập trình cơ bản” rồi mới học “Thuật toán”, phải đổ móng rồi mới xây tường, ô Excel B1 dùng A1 nên phải tính A1 trước. Khi các quan hệ “phải trước” này không vòng lại nhau, ta có một đồ thị có hướng không chu trình (DAG), và việc đầu tiên luôn là xếp các đỉnh theo thứ tự topo.
Bài này nối thẳng với hai bài trước của em: quy hoạch động ở bài 19 thực chất là đi trên một DAG các trạng thái, còn bài 29 cần Bellman–Ford chậm chạp khi có cạnh âm, thì trên DAG ta làm được trong $O(n + m)$. Đề HSG tỉnh và quốc gia rất hay giấu DAG dưới dạng “công việc”, “môn học”, “công thức phụ thuộc”, “xếp hạng”, nên nhận ra nó nhanh là lợi thế lớn.
priority_queue và bài xếp lịch công việc song song. Có khung chạy tay thuật toán Kahn, 3 mô phỏng tương tác và 8 bài tập kèm gợi ý.Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Đồ thị có hướng, DAG và thứ tự topo
Đồ thị có hướng gồm các đỉnh và các cạnh có hướng (cung) $u \to v$: đi được từ $u$ sang $v$ nhưng không đi ngược lại được. Với mỗi đỉnh $v$:
- bậc vào $deg_{in}(v)$ là số cạnh đi vào $v$;
- bậc ra $deg_{out}(v)$ là số cạnh đi ra khỏi $v$.
Lưu đồ thị vẫn bằng danh sách kề như bài 21, chỉ khác một chỗ: đọc cạnh u v thì chỉ thêm adj[u].push_back(v), không thêm chiều ngược lại. Tổng bậc vào bằng tổng bậc ra và bằng $m$.
Ví dụ môn học tiên quyết. Một trung tâm dạy 6 chuyên đề. Cạnh $u \to v$ nghĩa là “học xong $u$ mới được học $v$”:
Hình 1. Đồ thị môn học: 6 đỉnh, 7 cạnh có hướng. Đỉnh 2 và 5 (xanh dương) có bậc vào 0: học ngay được, không cần môn nào trước. Đỉnh 3 có bậc vào 2: phải chờ cả môn 5 và môn 2.
Xem code C++ / Python: đọc đồ thị có hướng, tính bậc vào và bậc ra (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int degIn[200005], degOut[200005];
vector<int> adj[200005];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v); // có hướng: chỉ thêm MỘT chiều u -> v
degOut[u]++;
degIn[v]++;
}
for(int v = 1; v <= n; v++) cout << degIn[v] << " ";
cout << "\n";
for(int v = 1; v <= n; v++) cout << degOut[v] << " ";
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
deg_in = [0] * (n + 1)
deg_out = [0] * (n + 1)
for i in range(m):
u, v = int(data[2 + 2 * i]), int(data[3 + 2 * i])
adj[u].append(v) # có hướng: chỉ thêm MỘT chiều u -> v
deg_out[u] += 1
deg_in[v] += 1
print(*deg_in[1:])
print(*deg_out[1:])Chu trình có hướng là một đường đi theo đúng chiều mũi tên rồi quay về đỉnh xuất phát, ví dụ $1 \to 2 \to 3 \to 1$. Đồ thị có hướng không có chu trình nào gọi là DAG (Directed Acyclic Graph). Đồ thị môn học ở Hình 1 là một DAG: nếu có chu trình thì môn A cần môn B, môn B lại cần môn A, không ai học được cả.
Thứ tự topo (topological order) của đồ thị có hướng là một cách xếp tất cả các đỉnh thành một hàng sao cho mọi cạnh $u \to v$ đều có $u$ đứng trước $v$. Với ví dụ môn học, đó chính là một lịch học hợp lệ. Xếp các đỉnh theo thứ tự 2, 5, 1, 3, 4, 6 trên một đường thẳng, em sẽ thấy mọi mũi tên đều chỉ sang phải:
Hình 2. Thứ tự topo 2, 5, 1, 3, 4, 6 của đồ thị Hình 1: cả 7 cạnh đều hướng từ trái sang phải. Chỉ cần một cạnh hướng sang trái là thứ tự hỏng.
| Thứ tự | Hợp lệ? | Lý do |
|---|---|---|
| 2 5 1 3 4 6 | có | mọi cạnh hướng sang phải (Hình 2) |
| 5 2 3 1 4 6 | có | cũng đúng: thứ tự topo thường không duy nhất |
| 5 1 2 4 3 6 | không | cạnh 3 → 4 nhưng 4 đứng trước 3 |
| 2 3 5 1 4 6 | không | cạnh 5 → 3 nhưng 3 đứng trước 5: học “Thuật toán cơ bản” khi chưa học “Lập trình cơ bản” |
Bảng 1. Kiểm tra một thứ tự: ghi pos[v] là vị trí của $v$ trong hàng, rồi duyệt mọi cạnh xem có $pos[u] < pos[v]$ không. Mất $O(n + m)$ (bài tập 1).
Khi nào có thứ tự topo? Đúng khi và chỉ khi đồ thị là DAG:
- Nếu có chu trình $v_1 \to v_2 \to \cdots \to v_k \to v_1$ thì $v_1$ phải đứng trước $v_2$, $v_2$ trước $v_3$, …, $v_k$ trước $v_1$: vô lý. Không xếp được.
- Nếu là DAG thì luôn có ít nhất một đỉnh bậc vào 0. Thật vậy, nếu đỉnh nào cũng có cạnh đi vào, em cứ đi ngược mũi tên mãi, sau tối đa $n$ bước sẽ gặp lại một đỉnh cũ, tức là có chu trình. Đặt đỉnh bậc vào 0 đó lên đầu hàng, xoá nó cùng các cạnh của nó, phần còn lại vẫn là DAG, lại có đỉnh bậc vào 0… Cứ thế ta xếp được hết.
Lập luận thứ hai chính là thuật toán Kahn ở phần sau.
Phần 2Thuật toán Kahn: xoá dần các đỉnh bậc vào 0
Thuật toán Kahn làm đúng như lập luận ở phần 1, giống hệt cách em tự lên lịch học:
- Tính bậc vào
deg[v]của mọi đỉnh. Cho tất cả đỉnh códeg = 0vào một hàng đợi. - Lấy đỉnh $u$ ở đầu hàng đợi, ghi $u$ vào cuối thứ tự topo.
- “Xoá” mọi cạnh $u \to v$: giảm
deg[v]đi 1. Nếudeg[v]về 0 thì $v$ không còn phải chờ ai, đẩy $v$ vào hàng đợi. - Lặp lại tới khi hàng đợi rỗng.
Ta không cần xoá cạnh thật; chỉ cần giảm bậc vào là đủ. Chạy trên đồ thị Hình 1:
| Bước | Lấy ra | Giảm bậc vào | Vào hàng đợi | Hàng đợi sau bước | Thứ tự |
|---|---|---|---|---|---|
| 0 | – | deg = [1, 0, 2, 2, 0, 2] (đỉnh 1..6) | 2, 5 | 2 5 | |
| 1 | 2 | deg[3]: 2 → 1 | 5 | 2 | |
| 2 | 5 | deg[1]: 1 → 0; deg[3]: 1 → 0 | 1, 3 | 1 3 | 2 5 |
| 3 | 1 | deg[4]: 2 → 1 | 3 | 2 5 1 | |
| 4 | 3 | deg[4]: 1 → 0; deg[6]: 2 → 1 | 4 | 4 | 2 5 1 3 |
| 5 | 4 | deg[6]: 1 → 0 | 6 | 6 | 2 5 1 3 4 |
| 6 | 6 | (không có cạnh ra) | (rỗng) | 2 5 1 3 4 6 |
Bảng 2. Thuật toán Kahn trên đồ thị Hình 1. Mỗi đỉnh vào và ra khỏi hàng đợi đúng một lần, mỗi cạnh bị “xoá” đúng một lần.
Xem code C++ / Python: thuật toán kahn, in thứ tự topo hoặc -1 nếu có chu trình (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int deg[200005];
vector<int> adj[200005];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
deg[v]++; // v phải chờ thêm một đỉnh
}
queue<int> q;
for(int u = 1; u <= n; u++)
if(deg[u] == 0) q.push(u); // không phải chờ ai
vector<int> order;
while(!q.empty()){
int u = q.front(); q.pop();
order.push_back(u);
for(int v : adj[u])
if(--deg[v] == 0) q.push(v); // v hết phải chờ
}
if((int)order.size() < n) cout << -1; // còn đỉnh kẹt lại: có chu trình
else for(int u : order) cout << u << " ";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
deg = [0] * (n + 1)
for i in range(m):
u, v = int(data[2 + 2 * i]), int(data[3 + 2 * i])
adj[u].append(v)
deg[v] += 1 # v phải chờ thêm một đỉnh
q = [u for u in range(1, n + 1) if deg[u] == 0]
head = 0 # q[head:] là phần còn trong hàng đợi
while head < len(q):
u = q[head]; head += 1
for v in adj[u]:
deg[v] -= 1
if deg[v] == 0: # v hết phải chờ
q.append(v)
if len(q) < n:
print(-1) # còn đỉnh kẹt lại: có chu trình
else:
print(*q) # q chính là thứ tự topo
main()Em chạy tay từng dòng để thấy mảng deg giảm dần và hàng đợi thay đổi thế nào. Thử thêm dữ liệu mẫu “có chu trình” để thấy vòng while dừng sớm:
Phát hiện chu trình. Nếu đồ thị có chu trình, các đỉnh trên chu trình chờ lẫn nhau theo vòng tròn: bậc vào của chúng không bao giờ về 0, nên chúng không bao giờ vào hàng đợi. Vậy chỉ cần đếm: lấy ra đủ $n$ đỉnh thì là DAG, thiếu thì có chu trình. Đỉnh nằm “sau” chu trình (như đỉnh 4 trong hình dưới) cũng bị kẹt theo.
Hình 3. Ba đỉnh 1 → 2 → 3 → 1 tạo chu trình, đỉnh nào cũng có bậc vào 1, hàng đợi rỗng ngay từ đầu. Đỉnh 4 không nằm trên chu trình nhưng phải chờ đỉnh 2 nên cũng kẹt.
Bảng và khung chạy tay cho em thấy từng con số, còn mô phỏng dưới đây cho em nhìn các cạnh lần lượt bị xoá trên chính đồ thị. Em sửa danh sách cạnh tuỳ ý, thử thêm cạnh “6 2” để tạo chu trình:
list.pop(0): mỗi lần mất $O(n)$, cả thuật toán thành $O(n^2)$. Dùng collections.deque, hoặc như code trên: giữ một biến head chạy trên list, list đó cuối cùng chính là thứ tự topo. Trong C++, mẹo tương tự là dùng luôn vector order làm hàng đợi (xem code phần 4).Phần 3Sắp xếp topo bằng DFS và kỹ thuật ba màu
Cách thứ hai dùng DFS của bài 21, với một nhận xét rất đẹp: khi dfs(u) chạy xong, mọi đỉnh mà $u$ đi tới được đều đã chạy xong trước đó. Vậy nếu ghi mỗi đỉnh vào một danh sách ngay lúc nó kết thúc, thì với mọi cạnh $u \to v$, đỉnh $v$ luôn được ghi trước $u$. Đảo ngược danh sách kết thúc là được thứ tự topo.
Chạy trên đồ thị Hình 1 (duyệt đỉnh 1, 2, …, 6, mỗi danh sách kề theo thứ tự nhập):
| Gọi | Diễn biến | Danh sách kết thúc |
|---|---|---|
| dfs(1) | 1 → 4 → 6; 6 không có cạnh ra, xong; 4 xong; 1 xong | 6, 4, 1 |
| dfs(2) | 2 → 3; cạnh 3 → 4 và 3 → 6 tới đỉnh đã xong, bỏ qua; 3 xong; 2 xong | 6, 4, 1, 3, 2 |
| dfs(5) | cạnh 5 → 1 và 5 → 3 tới đỉnh đã xong; 5 xong | 6, 4, 1, 3, 2, 5 |
| đảo ngược | 5, 2, 3, 1, 4, 6 |
Bảng 3. DFS cho thứ tự 5 2 3 1 4 6, khác với Kahn (2 5 1 3 4 6) nhưng cũng đúng (dòng 2 của Bảng 1).
Phát hiện chu trình: vì sao cần ba màu? Với đồ thị vô hướng ở bài 21, mảng visited hai trạng thái là đủ. Với đồ thị có hướng thì không: đồ thị $1 \to 2$, $1 \to 3$, $3 \to 2$ không có chu trình, nhưng khi đi $1 \to 3 \to 2$ ta gặp lại đỉnh 2 đã thăm. Gặp lại đỉnh đã thăm chưa nói lên điều gì. Ta cần phân biệt:
- Trắng (0): chưa thăm.
- Xám (1): đã vào
dfs(u)nhưng chưa ra, tức là $u$ đang nằm trên đường đi hiện tại (ngăn xếp đệ quy). - Đen (2): đã xong hẳn.
Đang ở $u$ mà gặp cạnh $u \to v$ với $v$ xám thì từ $v$ ta đã đi xuống tới $u$, giờ lại có cạnh quay về $v$: đó là cạnh ngược, khép thành chu trình. Gặp $v$ đen thì vô hại: $v$ đã xong, từ $v$ không quay về được $u$ (nếu được thì $u$ đã được thăm trong lúc chạy dfs(v)). Để in chu trình, lưu par[v] là đỉnh đã gọi xuống $v$, rồi lần ngược từ $u$ về $v$.
Đệ quy rất khó hình dung bằng chữ. Trong mô phỏng, hàng “Đang mở” chính là ngăn xếp đệ quy (các đỉnh xám). Em để ý: đỉnh được ghi vào “Kết thúc” khi nào, và vì sao gặp đỉnh xám thì dừng ngay:
Xem code C++ / Python: sắp xếp topo bằng dfs ba màu, in chu trình nếu có (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int color[200005], par[200005]; // 0 trắng, 1 xám, 2 đen
vector<int> adj[200005], order;
int cs = -1, ce = -1; // cạnh ngược ce -> cs khép chu trình
bool dfs(int u){ // trả về true nếu tìm thấy chu trình
color[u] = 1; // xám: đang mở
for(int v : adj[u]){
if(color[v] == 0){
par[v] = u;
if(dfs(v)) return true;
}
else if(color[v] == 1){ // gặp đỉnh xám: cạnh ngược
cs = v; ce = u;
return true;
} // đỉnh đen: bỏ qua
}
color[u] = 2; // đen: đã xong
order.push_back(u); // ghi vào thứ tự kết thúc
return false;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
}
for(int u = 1; u <= n; u++)
if(color[u] == 0 && dfs(u)) break;
if(cs != -1){
vector<int> cyc;
for(int x = ce; x != cs; x = par[x]) cyc.push_back(x);
cyc.push_back(cs);
reverse(cyc.begin(), cyc.end()); // cs -> ... -> ce
cout << "CYCLE\n";
for(int x : cyc) cout << x << " ";
cout << cs; // quay về đỉnh đầu
} else {
reverse(order.begin(), order.end()); // đảo ngược thứ tự kết thúc
for(int x : order) cout << x << " ";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
for i in range(m):
adj[int(data[2 + 2 * i])].append(int(data[3 + 2 * i]))
color = [0] * (n + 1) # 0 trắng, 1 xám, 2 đen
par = [0] * (n + 1)
it = [0] * (n + 1) # it[u]: cạnh tiếp theo cần xét của u
order = []
for s in range(1, n + 1):
if color[s]:
continue
stack = [s]; color[s] = 1 # DFS khử đệ quy, stack = các đỉnh xám
while stack:
u = stack[-1]
if it[u] < len(adj[u]):
v = adj[u][it[u]]; it[u] += 1
if color[v] == 0:
par[v] = u; color[v] = 1; stack.append(v)
elif color[v] == 1: # cạnh ngược u -> v
cyc = [u]
while cyc[-1] != v:
cyc.append(par[cyc[-1]])
cyc.reverse() # v -> ... -> u
print("CYCLE")
print(*(cyc + [v]))
return
else:
color[u] = 2 # đen: đã xong
order.append(u)
stack.pop()
order.reverse() # đảo ngược thứ tự kết thúc
print(*order)
main()setrecursionlimit vẫn dễ bị tràn ngăn xếp. Bản Python ở trên tự quản lý ngăn xếp: it[u] nhớ cạnh tiếp theo cần xét của $u$, đỉnh ở đỉnh ngăn xếp hết cạnh thì tô đen và lấy ra. Nếu chỉ cần thứ tự topo mà không cần in chu trình, Kahn là lựa chọn an toàn hơn vì không đệ quy.| Kahn (BFS) | DFS ba màu | |
|---|---|---|
| Ý tưởng | lấy dần đỉnh bậc vào 0 | đảo ngược thứ tự kết thúc |
| Độ phức tạp | $O(n + m)$ | $O(n + m)$ |
| Phát hiện chu trình | đếm số đỉnh lấy ra < $n$ | gặp cạnh tới đỉnh xám |
| In ra một chu trình | khó hơn | dễ: lần theo par |
| Từ điển nhỏ nhất | đổi queue thành priority_queue | không làm được trực tiếp |
| Chia lớp (học kỳ) | tự nhiên: theo từng đợt lấy ra | phải tính thêm |
| Đệ quy | không | có (Python nên khử) |
Bảng 4. Hai cách sắp xếp topo. Khi đi thi, mặc định dùng Kahn; dùng DFS khi cần in chu trình hoặc khi đang DFS sẵn cho việc khác.
Phần 4Quy hoạch động trên DAG
Nhớ lại bài 19: mỗi bài quy hoạch động có các trạng thái và công thức truy hồi “trạng thái này tính từ những trạng thái kia”. Vẽ mỗi trạng thái là một đỉnh, mỗi phụ thuộc là một cạnh, em được một DAG (không có chu trình, nếu không công thức sẽ tự gọi lại chính nó). Thứ tự tính for i = 1..n quen thuộc thực chất là một thứ tự topo của DAG đó. Ngược lại, trên một DAG bất kỳ, chỉ cần xếp topo rồi tính theo đúng thứ tự là làm được quy hoạch động.
Bài toán. Cho DAG có trọng số, đỉnh nguồn $s$. Với mỗi đỉnh $v$, tính:
- $dp[v]$ = độ dài đường đi dài nhất từ $s$ tới $v$ ($-\infty$ nếu không tới được);
- $cnt[v]$ = số đường đi khác nhau từ $s$ tới $v$, lấy theo modulo $10^9 + 7$.
Khởi tạo $dp[s] = 0$, $cnt[s] = 1$. Duyệt các đỉnh $u$ theo thứ tự topo; với mỗi cạnh $u \to v$ dài $w$, đẩy giá trị sang $v$:
$dp[v] = \max(dp[v],\ dp[u] + w), \qquad cnt[v] \mathrel{+}= cnt[u].$
Vì sao đúng? Khi tới lượt $u$, mọi cạnh đi vào $u$ đều xuất phát từ đỉnh đứng trước $u$ trong thứ tự topo, và những đỉnh đó đã đẩy giá trị sang $u$ xong. Vậy $dp[u]$, $cnt[u]$ đã là đáp án cuối cùng trước khi được dùng. Mỗi cạnh xét đúng một lần: $O(n + m)$.
Lấy lại đồ thị Hình 1, gắn thêm độ dài cho các cạnh: 5→1 (3), 5→3 (2), 2→3 (4), 1→4 (1), 3→4 (1), 3→6 (4), 4→6 (5), và chọn $s = 5$. Thứ tự topo theo Kahn là 2, 5, 1, 3, 4, 6:
| Đỉnh u | Cạnh đẩy đi | dp sau bước | cnt sau bước |
|---|---|---|---|
| 2 | dp[2] = −∞: bỏ qua (5 không tới được 2) | 5:0 | 5:1 |
| 5 | 5→1: 0 + 3; 5→3: 0 + 2 | 1:3, 3:2 | 1:1, 3:1 |
| 1 | 1→4: 3 + 1 = 4 | 4:4 | 4:1 |
| 3 | 3→4: 2 + 1 = 3 < 4, giữ 4; 3→6: 2 + 4 = 6 | 4:4, 6:6 | 4:2, 6:1 |
| 4 | 4→6: 4 + 5 = 9 > 6 | 6:9 | 6:3 |
| 6 | (không có cạnh ra) | dp[6] = 9 | cnt[6] = 3 |
Bảng 5. Từ 5 tới 6 có 3 đường: 5→1→4→6 (dài 9), 5→3→4→6 (dài 8), 5→3→6 (dài 6). Đường dài nhất là 9.
Em xem từng cạnh được “đẩy” trong mô phỏng. Đổi nguồn $s$ thành 2 để thấy đỉnh 5 và 1 không tới được (giữ $-\infty$), hoặc tự nhập DAG khác:
Xem code C++ / Python: đường đi dài nhất và số đường đi trên dag (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007, NEG = LLONG_MIN;
int deg[200005];
vector<pair<int, int>> adj[200005]; // (đỉnh kề, độ dài cạnh)
long long dp[200005], cnt[200005];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m, s, t;
cin >> n >> m >> s >> t;
for(int i = 0; i < m; i++){
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
deg[v]++;
}
// Bước 1: thứ tự topo bằng Kahn (vector order dùng luôn làm hàng đợi)
vector<int> order;
for(int u = 1; u <= n; u++) if(deg[u] == 0) order.push_back(u);
for(int i = 0; i < (int)order.size(); i++)
for(auto e : adj[order[i]])
if(--deg[e.first] == 0) order.push_back(e.first);
// Bước 2: quy hoạch động theo thứ tự topo
for(int u = 1; u <= n; u++){ dp[u] = NEG; cnt[u] = 0; }
dp[s] = 0; cnt[s] = 1;
for(int u : order){
if(dp[u] == NEG) continue; // s không tới được u
for(auto e : adj[u]){
int v = e.first, w = e.second;
dp[v] = max(dp[v], dp[u] + w); // đường đi dài nhất
cnt[v] = (cnt[v] + cnt[u]) % MOD; // số đường đi
}
}
cout << (dp[t] == NEG ? -1 : dp[t]) << "\n" << cnt[t];
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m, s, t = int(data[0]), int(data[1]), int(data[2]), int(data[3])
MOD = 10**9 + 7
adj = [[] for _ in range(n + 1)]
deg = [0] * (n + 1)
for i in range(m):
u, v, w = int(data[4 + 3 * i]), int(data[5 + 3 * i]), int(data[6 + 3 * i])
adj[u].append((v, w))
deg[v] += 1
order = [u for u in range(1, n + 1) if deg[u] == 0] # Bước 1: Kahn
for u in order: # list dài thêm trong lúc duyệt
for v, w in adj[u]:
deg[v] -= 1
if deg[v] == 0:
order.append(v)
dp = [None] * (n + 1) # None nghĩa là -vô cùng
cnt = [0] * (n + 1)
dp[s], cnt[s] = 0, 1
for u in order: # Bước 2: QHĐ
if dp[u] is None:
continue
for v, w in adj[u]:
if dp[v] is None or dp[u] + w > dp[v]:
dp[v] = dp[u] + w
cnt[v] = (cnt[v] + cnt[u]) % MOD
print(-1 if dp[t] is None else dp[t])
print(cnt[t])
main()2. Tràn số. Độ dài tới $10^9 \cdot 2 \cdot 10^5$: dùng
long long. Số đường đi tăng theo cấp số nhân: luôn lấy modulo sau mỗi phép cộng.3. Đường dài nhất trên đồ thị có chu trình là bài toán cực khó (chưa ai biết cách giải nhanh). Chỉ trên DAG mới làm được trong $O(n + m)$.
Đường đi ngắn nhất có cạnh âm. Thay max bằng min và $-\infty$ bằng $+\infty$, em được đường đi ngắn nhất trên DAG trong $O(n + m)$, kể cả khi có cạnh âm. Ở bài 29, Dijkstra sai khi có cạnh âm và Bellman–Ford mất $O(nm)$; nếu đề cho DAG thì đây là cách nhanh nhất.
// 1. order = thứ tự topo (Kahn)
// 2. khởi tạo dp[nguồn], các đỉnh khác = giá trị "chưa có"
for(int u : order){
if(dp[u] chưa có) continue;
for(auto [v, w] : adj[u])
dp[v] = gop(dp[v], chuyen(dp[u], w)); // max, min, +, ...
}Phần 5Thứ tự topo nhỏ nhất theo từ điển và xếp lịch công việc
Thứ tự nhỏ nhất theo từ điển. Trong các thứ tự topo, cần in thứ tự mà so sánh như so sánh xâu (phần tử đầu tiên khác nhau nhỏ hơn) là nhỏ nhất. Tham lam: ở mỗi bước, trong các đỉnh đang “rảnh” (bậc vào 0), lấy đỉnh có số nhỏ nhất. Vì đỉnh nào đang rảnh cũng hợp lệ để đặt tiếp theo, chọn số nhỏ nhất chắc chắn làm vị trí này nhỏ nhất có thể, và không làm mất lựa chọn nào của các vị trí sau (các đỉnh rảnh khác vẫn rảnh). Chỉ cần thay queue trong Kahn bằng priority_queue lấy số nhỏ trước: $O((n + m) \log n)$.
Ví dụ $n = 4$, hai cạnh $4 \to 1$ và $2 \to 3$:
| Bước | Kahn với queue | Kahn với priority_queue (min) |
|---|---|---|
| Ban đầu | hàng đợi: 2 4 | đống: {2, 4} |
| 1 | lấy 2, đẩy 3 vào cuối → 4 3 | lấy 2, thêm 3 → {3, 4} |
| 2 | lấy 4, đẩy 1 vào cuối → 3 1 | lấy 3 (nhỏ hơn 4) → {4} |
| 3 | lấy 3 → 1 | lấy 4, thêm 1 → {1} |
| 4 | lấy 1 | lấy 1 |
| Kết quả | 2 4 3 1 | 2 3 4 1 |
Bảng 6. Hàng đợi thường cho thứ tự đúng nhưng chưa nhỏ nhất. Hàng đợi ưu tiên luôn chọn đỉnh rảnh có số nhỏ nhất.
Xem code C++ / Python: thứ tự topo nhỏ nhất theo từ điển với priority_queue (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int deg[200005];
vector<int> adj[200005];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
deg[v]++;
}
priority_queue<int, vector<int>, greater<int>> pq; // hàng đợi ưu tiên: số nhỏ ra trước
for(int u = 1; u <= n; u++)
if(deg[u] == 0) pq.push(u);
vector<int> order;
while(!pq.empty()){
int u = pq.top(); pq.pop(); // đỉnh "rảnh" có số nhỏ nhất
order.push_back(u);
for(int v : adj[u])
if(--deg[v] == 0) pq.push(v);
}
if((int)order.size() < n) cout << -1;
else for(int u : order) cout << u << " ";
return 0;
}import sys, heapq
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
deg = [0] * (n + 1)
for i in range(m):
u, v = int(data[2 + 2 * i]), int(data[3 + 2 * i])
adj[u].append(v)
deg[v] += 1
pq = [u for u in range(1, n + 1) if deg[u] == 0] # đã tăng dần nên là heap hợp lệ
order = []
while pq:
u = heapq.heappop(pq) # đỉnh "rảnh" có số nhỏ nhất
order.append(u)
for v in adj[u]:
deg[v] -= 1
if deg[v] == 0:
heapq.heappush(pq, v)
print(-1 if len(order) < n else ' '.join(map(str, order)))
main()Xếp lịch công việc song song. Dự án có $n$ công việc, việc $v$ mất $t_v$ ngày. Có $m$ điều kiện “việc $u$ xong thì việc $v$ mới được bắt đầu”. Có đủ người để làm song song mọi việc không phụ thuộc nhau. Hỏi dự án xong sớm nhất sau bao nhiêu ngày?
Gọi $f[v]$ là thời điểm sớm nhất làm xong việc $v$. Việc $v$ chỉ bắt đầu được khi mọi việc phải làm trước nó đã xong, nên:
$f[v] = t_v + \max_{u \to v} f[u]$ (bằng $t_v$ nếu $v$ không phải chờ ai), đáp án $= \max_v f[v]$.
Đây chính là QHĐ trên DAG của phần 4, trọng số nằm ở đỉnh thay vì ở cạnh: đáp án là đường đi dài nhất (tính tổng thời gian các việc trên đường). Đường đi đó gọi là đường găng (critical path): chỉ cần một việc trên đường găng trễ là cả dự án trễ (bài tập 7). Với đồ thị Hình 1 và thời gian $t = (2, 3, 4, 1, 2, 3)$ cho việc 1..6:
| Việc (theo thứ tự topo) | 2 | 5 | 1 | 3 | 4 | 6 |
|---|---|---|---|---|---|---|
| $t_v$ | 3 | 2 | 2 | 4 | 1 | 3 |
| phải chờ | – | – | 5 | 5, 2 | 1, 3 | 3, 4 |
| $f[v]$ | 3 | 2 | 2 + 2 = 4 | 4 + max(2, 3) = 7 | 1 + max(4, 7) = 8 | 3 + max(7, 8) = 11 |
Bảng 7. Dự án xong sớm nhất sau 11 ngày. Đường găng là 2 → 3 → 4 → 6 (3 + 4 + 1 + 3 = 11 ngày). Nếu mọi việc đều mất 1 ngày, $f[v]$ chính là số học kỳ ít nhất để học xong môn $v$ (bài tập 4).
Xem code C++ / Python: thời gian hoàn thành sớm nhất của dự án (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int deg[200005];
long long t[200005], f[200005]; // f[v]: thời điểm sớm nhất làm xong việc v
vector<int> adj[200005];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
for(int v = 1; v <= n; v++) cin >> t[v];
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v; // u xong thì v mới được bắt đầu
adj[u].push_back(v);
deg[v]++;
}
vector<int> order;
for(int v = 1; v <= n; v++){
f[v] = t[v]; // không phải chờ ai thì xong ở thời điểm t[v]
if(deg[v] == 0) order.push_back(v);
}
for(int i = 0; i < (int)order.size(); i++){
int u = order[i];
for(int v : adj[u]){
f[v] = max(f[v], f[u] + t[v]); // v bắt đầu sau khi u xong
if(--deg[v] == 0) order.push_back(v);
}
}
if((int)order.size() < n){ cout << -1; return 0; }
cout << *max_element(f + 1, f + n + 1);
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
t = [0] + [int(x) for x in data[2:2 + n]]
adj = [[] for _ in range(n + 1)]
deg = [0] * (n + 1)
p = 2 + n
for i in range(m):
u, v = int(data[p + 2 * i]), int(data[p + 2 * i + 1]) # u xong thì v mới bắt đầu
adj[u].append(v)
deg[v] += 1
f = t[:] # f[v]: thời điểm sớm nhất làm xong v
order = [v for v in range(1, n + 1) if deg[v] == 0]
for u in order:
for v in adj[u]:
if f[u] + t[v] > f[v]:
f[v] = f[u] + t[v]
deg[v] -= 1
if deg[v] == 0:
order.append(v)
print(-1 if len(order) < n else max(f[1:]))
main()- Covid (ICTU P58) (Trung bình)
- Số Cách Đi Quân Mã (SOCACH) (Olympic 30/4 2023 – Tin học khối 10) (Khá)
- Strange Printer II (LeetCode 1591) (Khó)
- Parallel Courses II (LeetCode 1494) (Khó)
- Count Ways to Build Rooms in an Ant Colony (LeetCode 1916) (Khó)
Bài tậpLuyện sắp xếp topo và QHĐ trên DAG
Có $n$ môn học ($n, m \le 2 \cdot 10^5$) và $m$ điều kiện “học môn $u$ trước môn $v$”. Bạn Tí đưa ra lịch học là một hoán vị $p_1, p_2, \ldots, p_n$ của $1..n$ (học $p_1$ trước, rồi $p_2$…). In YES nếu lịch thoả mọi điều kiện, ngược lại in NO.
Input: dòng đầu $n, m$; $m$ dòng tiếp mỗi dòng $u, v$; dòng cuối là hoán vị $p$.
6 7
5 1
5 3
2 3
1 4
3 4
3 6
4 6
5 2 3 1 4 6YES📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
pos[p_i] = i, rồi duyệt lại mọi cạnh: chỉ cần một cạnh có $pos[u] > pos[v]$ là NO. Phải lưu cạnh lại vì hoán vị nằm ở cuối input. Ví dụ chính là dòng 2 của Bảng 1, mọi cạnh đều hướng về phía sau.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int eu[200005], ev[200005], pos[200005];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++) cin >> eu[i] >> ev[i];
for(int i = 1; i <= n; i++){
int p;
cin >> p;
pos[p] = i; // môn p học ở vị trí i
}
for(int i = 0; i < m; i++)
if(pos[eu[i]] >= pos[ev[i]]){ cout << "NO"; return 0; }
cout << "YES";
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
edges = data[2:2 + 2 * m]
pos = [0] * (n + 1)
for i, x in enumerate(data[2 + 2 * m:2 + 2 * m + n]):
pos[int(x)] = i # môn x học ở vị trí i
ok = all(pos[int(edges[2 * i])] < pos[int(edges[2 * i + 1])] for i in range(m))
print("YES" if ok else "NO")Có $n$ môn học và $m$ điều kiện “học $u$ trước $v$” ($n, m \le 2 \cdot 10^5$, có thể có $u = v$ do nhập nhầm). Hỏi có thể học hết $n$ môn không? In YES hoặc NO.
4 4
1 2
2 3
3 1
3 4NO📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
YES. Cạnh $u \to u$ là một chu trình độ dài 1: bậc vào của $u$ không bao giờ về 0, Kahn tự xử lý đúng. Ví dụ: 1 → 2 → 3 → 1 là chu trình (Hình 3).Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int deg[200005];
vector<int> adj[200005];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
deg[v]++;
}
vector<int> q;
for(int u = 1; u <= n; u++) if(deg[u] == 0) q.push_back(u);
for(int i = 0; i < (int)q.size(); i++)
for(int v : adj[q[i]])
if(--deg[v] == 0) q.push_back(v);
cout << ((int)q.size() == n ? "YES" : "NO");
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
deg = [0] * (n + 1)
for i in range(m):
u, v = int(data[2 + 2 * i]), int(data[3 + 2 * i])
adj[u].append(v)
deg[v] += 1
q = [u for u in range(1, n + 1) if deg[u] == 0]
for u in q:
for v in adj[u]:
deg[v] -= 1
if deg[v] == 0:
q.append(v)
print("YES" if len(q) == n else "NO")Có $n$ môn học đánh số $1..n$ và $m$ điều kiện “học $u$ trước $v$” ($n, m \le 2 \cdot 10^5$). Mỗi ngày học đúng một môn. Trong mọi lịch học hợp lệ, hãy in lịch nhỏ nhất theo thứ tự từ điển. Nếu không có lịch hợp lệ, in -1.
5 4
5 2
3 4
5 1
4 13 4 5 1 2📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
priority_queue lấy số nhỏ nhất (phần 5). Ban đầu rảnh: 3, 5. Lấy 3 → 4 rảnh; rảnh {4, 5}, lấy 4 (1 còn chờ 5); lấy 5 → 1 và 2 rảnh; lấy 1, lấy 2.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int deg[200005];
vector<int> adj[200005];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
deg[v]++;
}
priority_queue<int, vector<int>, greater<int>> pq; // hàng đợi ưu tiên: số nhỏ ra trước
for(int u = 1; u <= n; u++)
if(deg[u] == 0) pq.push(u);
vector<int> order;
while(!pq.empty()){
int u = pq.top(); pq.pop(); // đỉnh "rảnh" có số nhỏ nhất
order.push_back(u);
for(int v : adj[u])
if(--deg[v] == 0) pq.push(v);
}
if((int)order.size() < n) cout << -1;
else for(int u : order) cout << u << " ";
return 0;
}import sys, heapq
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
deg = [0] * (n + 1)
for i in range(m):
u, v = int(data[2 + 2 * i]), int(data[3 + 2 * i])
adj[u].append(v)
deg[v] += 1
pq = [u for u in range(1, n + 1) if deg[u] == 0] # đã tăng dần nên là heap hợp lệ
order = []
while pq:
u = heapq.heappop(pq) # đỉnh "rảnh" có số nhỏ nhất
order.append(u)
for v in adj[u]:
deg[v] -= 1
if deg[v] == 0:
heapq.heappush(pq, v)
print(-1 if len(order) < n else ' '.join(map(str, order)))
main()Có $n$ môn học và $m$ điều kiện “học $u$ trước $v$” ($n, m \le 2 \cdot 10^5$). Mỗi học kỳ được học bao nhiêu môn cũng được, miễn là mọi môn tiên quyết của chúng đã học xong ở các học kỳ trước. Hỏi cần ít nhất bao nhiêu học kỳ để học hết? In -1 nếu không thể.
6 7
5 1
5 3
2 3
1 4
3 4
3 6
4 64📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int deg[200005], sem[200005];
vector<int> adj[200005];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
deg[v]++;
}
vector<int> q;
for(int u = 1; u <= n; u++){
sem[u] = 1;
if(deg[u] == 0) q.push_back(u);
}
for(int i = 0; i < (int)q.size(); i++){
int u = q[i];
for(int v : adj[u]){
sem[v] = max(sem[v], sem[u] + 1); // v học sau u ít nhất một kỳ
if(--deg[v] == 0) q.push_back(v);
}
}
if((int)q.size() < n) cout << -1;
else cout << *max_element(sem + 1, sem + n + 1);
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
deg = [0] * (n + 1)
for i in range(m):
u, v = int(data[2 + 2 * i]), int(data[3 + 2 * i])
adj[u].append(v)
deg[v] += 1
sem = [1] * (n + 1)
q = [u for u in range(1, n + 1) if deg[u] == 0]
for u in q:
for v in adj[u]:
if sem[u] + 1 > sem[v]:
sem[v] = sem[u] + 1 # v học sau u ít nhất một kỳ
deg[v] -= 1
if deg[v] == 0:
q.append(v)
print(-1 if len(q) < n else max(sem[1:]))Có $n$ thành phố và $m$ chuyến bay một chiều ($2 \le n \le 10^5$, $m \le 2 \cdot 10^5$, có thể có nhiều chuyến cùng cặp thành phố). Đảm bảo không có cách nào bay vòng về chỗ cũ. Đếm số hành trình khác nhau từ thành phố 1 tới thành phố $n$, lấy phần dư khi chia cho $10^9 + 7$. Hai hành trình khác nhau nếu dãy chuyến bay khác nhau.
5 7
1 2
1 3
2 3
2 4
3 4
3 5
4 55📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int deg[100005];
long long cnt[100005];
vector<int> adj[100005];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
deg[v]++;
}
vector<int> q;
for(int u = 1; u <= n; u++) if(deg[u] == 0) q.push_back(u);
cnt[1] = 1;
for(int i = 0; i < (int)q.size(); i++){
int u = q[i];
for(int v : adj[u]){
cnt[v] = (cnt[v] + cnt[u]) % MOD;
if(--deg[v] == 0) q.push_back(v);
}
}
cout << cnt[n];
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
MOD = 10**9 + 7
adj = [[] for _ in range(n + 1)]
deg = [0] * (n + 1)
for i in range(m):
u, v = int(data[2 + 2 * i]), int(data[3 + 2 * i])
adj[u].append(v)
deg[v] += 1
cnt = [0] * (n + 1)
cnt[1] = 1
q = [u for u in range(1, n + 1) if deg[u] == 0]
for u in q:
c = cnt[u]
for v in adj[u]:
cnt[v] = (cnt[v] + c) % MOD
deg[v] -= 1
if deg[v] == 0:
q.append(v)
print(cnt[n])Có $n$ thành phố và $m$ tuyến xe một chiều ($2 \le n \le 10^5$, $m \le 2 \cdot 10^5$), đảm bảo không có tuyến nào quay vòng. Bạn Tèo đi từ thành phố 1 tới thành phố $n$ và muốn ghé qua nhiều thành phố nhất. In số thành phố tối đa trên hành trình (tính cả 1 và $n$), hoặc IMPOSSIBLE nếu không tới được $n$.
5 5
1 2
2 5
1 3
3 4
4 54📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
trace[v] = u khi cập nhật.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int deg[100005], dp[100005]; // dp[v] = 0: chưa tới được từ 1
vector<int> adj[100005];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
deg[v]++;
}
vector<int> q;
for(int u = 1; u <= n; u++) if(deg[u] == 0) q.push_back(u);
dp[1] = 1;
for(int i = 0; i < (int)q.size(); i++){
int u = q[i];
for(int v : adj[u]){
if(dp[u] > 0) dp[v] = max(dp[v], dp[u] + 1);
if(--deg[v] == 0) q.push_back(v);
}
}
if(dp[n] == 0) cout << "IMPOSSIBLE";
else cout << dp[n];
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
deg = [0] * (n + 1)
for i in range(m):
u, v = int(data[2 + 2 * i]), int(data[3 + 2 * i])
adj[u].append(v)
deg[v] += 1
dp = [0] * (n + 1) # 0: chưa tới được từ 1
dp[1] = 1
q = [u for u in range(1, n + 1) if deg[u] == 0]
for u in q:
for v in adj[u]:
if dp[u] and dp[u] + 1 > dp[v]:
dp[v] = dp[u] + 1
deg[v] -= 1
if deg[v] == 0:
q.append(v)
print(dp[n] if dp[n] else "IMPOSSIBLE")Dự án gồm $n$ công việc ($n \le 10^5$), việc $v$ mất $t_v$ ngày ($1 \le t_v \le 10^9$), và $m \le 2 \cdot 10^5$ điều kiện “việc $u$ xong thì việc $v$ mới được bắt đầu” (đảm bảo không có vòng). Có đủ người làm song song. In ra: dòng 1 là số ngày ít nhất để xong dự án $T$; dòng 2 là các việc then chốt theo thứ tự tăng dần, tức là những việc mà chỉ cần trễ 1 ngày thì cả dự án không thể xong trong $T$ ngày nữa.
Input: dòng đầu $n, m$; dòng hai $t_1..t_n$; $m$ dòng tiếp mỗi dòng $u, v$.
6 7
2 3 4 1 2 3
5 1
5 3
2 3
1 4
3 4
3 6
4 611
2 3 4 6📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int deg[100005];
long long t[100005], EF[100005], LF[100005];
vector<int> adj[100005];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
for(int v = 1; v <= n; v++) cin >> t[v];
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
deg[v]++;
}
vector<int> q;
for(int v = 1; v <= n; v++){
EF[v] = t[v];
if(deg[v] == 0) q.push_back(v);
}
for(int i = 0; i < (int)q.size(); i++){
int u = q[i];
for(int v : adj[u]){
EF[v] = max(EF[v], EF[u] + t[v]);
if(--deg[v] == 0) q.push_back(v);
}
}
long long T = *max_element(EF + 1, EF + n + 1);
for(int i = n - 1; i >= 0; i--){ // thứ tự topo ngược
int u = q[i];
LF[u] = T;
for(int v : adj[u]) LF[u] = min(LF[u], LF[v] - t[v]);
}
cout << T << "\n";
for(int v = 1; v <= n; v++)
if(EF[v] == LF[v]) cout << v << " ";
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
t = [0] + [int(x) for x in data[2:2 + n]]
adj = [[] for _ in range(n + 1)]
deg = [0] * (n + 1)
p = 2 + n
for i in range(m):
u, v = int(data[p + 2 * i]), int(data[p + 2 * i + 1])
adj[u].append(v)
deg[v] += 1
EF = t[:]
q = [v for v in range(1, n + 1) if deg[v] == 0]
for u in q:
for v in adj[u]:
if EF[u] + t[v] > EF[v]:
EF[v] = EF[u] + t[v]
deg[v] -= 1
if deg[v] == 0:
q.append(v)
T = max(EF[1:])
LF = [0] * (n + 1)
for u in reversed(q): # thứ tự topo ngược
LF[u] = min([T] + [LF[v] - t[v] for v in adj[u]])
print(T)
print(*[v for v in range(1, n + 1) if EF[v] == LF[v]])Người ngoài hành tinh dùng $k$ chữ cái đầu tiên của bảng chữ cái Latin thường ($1 \le k \le 26$) nhưng theo một thứ tự khác. Em nhặt được cuốn từ điển của họ gồm $n$ từ ($n \le 1000$, mỗi từ dài không quá 100) đã được sắp xếp tăng dần theo thứ tự của họ (so sánh như từ điển: chữ đầu tiên khác nhau quyết định; nếu từ này là tiền tố của từ kia thì từ ngắn hơn đứng trước). Hãy in một thứ tự của $k$ chữ cái phù hợp với cuốn từ điển; nếu có nhiều thứ tự, in thứ tự nhỏ nhất theo bảng chữ cái thông thường; nếu không có, in -1.
4 5
cc
cb
ba
bd
adcbad📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int k, n;
cin >> k >> n;
vector<string> w(n);
for(auto &s : w) cin >> s;
vector<int> adj[26];
int deg[26] = {0};
for(int i = 0; i + 1 < n; i++){
string &a = w[i], &b = w[i + 1];
int j = 0;
while(j < (int)a.size() && j < (int)b.size() && a[j] == b[j]) j++;
if(j == (int)a.size() || j == (int)b.size()){
if(a.size() > b.size()){ cout << -1; return 0; } // từ dài đứng trước tiền tố của nó
continue;
}
adj[a[j] - 'a'].push_back(b[j] - 'a'); // chữ a[j] đứng trước chữ b[j]
deg[b[j] - 'a']++;
}
priority_queue<int, vector<int>, greater<int>> pq;
for(int c = 0; c < k; c++) if(deg[c] == 0) pq.push(c);
string res;
while(!pq.empty()){
int c = pq.top(); pq.pop();
res += char('a' + c);
for(int d : adj[c]) if(--deg[d] == 0) pq.push(d);
}
if((int)res.size() < k) cout << -1;
else cout << res;
return 0;
}import sys, heapq
def main():
data = sys.stdin.read().split()
k, n = int(data[0]), int(data[1])
w = data[2:2 + n]
adj = [[] for _ in range(26)]
deg = [0] * 26
for a, b in zip(w, w[1:]):
j = 0
while j < len(a) and j < len(b) and a[j] == b[j]:
j += 1
if j == len(a) or j == len(b):
if len(a) > len(b): # từ dài đứng trước tiền tố của nó
print(-1)
return
continue
x, y = ord(a[j]) - 97, ord(b[j]) - 97 # chữ x đứng trước chữ y
adj[x].append(y)
deg[y] += 1
pq = [c for c in range(k) if deg[c] == 0]
res = []
while pq:
c = heapq.heappop(pq)
res.append(chr(97 + c))
for d in adj[c]:
deg[d] -= 1
if deg[d] == 0:
heapq.heappush(pq, d)
print(-1 if len(res) < k else ''.join(res))
main()
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét