Bài 36: Thành phần liên thông mạnh, đỉnh khớp và cầu trong C++ và Python: num/low, Tarjan, Kosaraju
Lời mở đầu
Ở bài 21 em đã dùng DFS để đếm thành phần liên thông: hai đỉnh cùng thành phần nếu đi được tới nhau. Nhưng đề thi HSG thường hỏi sâu hơn một bậc: “con đường nào mà bị sập thì mạng lưới bị chia cắt?”, “thành phố nào là điểm trung chuyển sống còn?”, hay với đường một chiều: “những nút nào đi qua đi lại được với nhau?”. Thử xoá từng cạnh rồi DFS lại thì tốn $O(m(n + m))$, quá chậm với $10^5$ cạnh.
Bài này dạy em một ý tưởng rất đẹp của Robert Tarjan: trong lúc DFS, ghi cho mỗi đỉnh thời điểm thăm num[u] và đỉnh thăm sớm nhất mà cây con của nó “với” tới được low[u]. Từ hai mảng ấy suy ra cùng lúc cầu, khớp và thành phần liên thông mạnh trong $O(n + m)$. Em nên ôn lại cây DFS ở bài 33 và đồ thị không có chu trình (DAG) ở bài 35, vì cuối bài ta sẽ nén mỗi thành phần liên thông mạnh thành một đỉnh và nhận được đúng một DAG để quy hoạch động.
Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Cây DFS, cạnh ngược, num[u] và low[u]
Chạy DFS trên đồ thị vô hướng liên thông, mỗi lần đi từ u sang một đỉnh v chưa thăm ta được một cạnh cây. Các cạnh cây tạo thành cây DFS có gốc là đỉnh xuất phát. Mọi cạnh còn lại gọi là cạnh ngược: chúng luôn nối một đỉnh với một tổ tiên của nó trên cây. Đồ thị vô hướng không có “cạnh ngang” nối hai nhánh khác nhau, vì nếu có cạnh $u$–$v$ mà $v$ chưa thăm lúc đang ở $u$ thì DFS đã đi sang $v$ ngay và biến nó thành cạnh cây rồi.
Ta ghi thêm hai số cho mỗi đỉnh:
- num[u]: thời điểm thăm $u$ (đỉnh thứ mấy được DFS chạm tới). Tổ tiên luôn có num nhỏ hơn con cháu.
- low[u]: num nhỏ nhất mà từ cây con gốc $u$ “với” tới được, khi được đi xuống tuỳ ý theo cạnh cây rồi dùng tối đa một cạnh ngược. Nói nôm na: low[u] cho biết cây con của $u$ có đường vòng leo lên cao tới đâu mà không cần đi qua cạnh nối $u$ với cha.
Công thức tính low trong lúc DFS rất gọn:
$\text{low}[u] = \min\big(\text{num}[u],\ \text{num}[v] \text{ với mọi cạnh ngược } u\text{–}v,\ \text{low}[c] \text{ với mọi con } c \text{ của } u\big)$
Hình 1. DFS từ đỉnh 1 (xét kề theo thứ tự nhập). Tím đậm: cạnh cây, nét đứt cam: cạnh ngược 3–1 và 6–4. Số cạnh mỗi đỉnh là num/low.
| Đỉnh | num | Cách tính low | low |
|---|---|---|---|
| 8 | 8 | không có con, không có cạnh ngược | 8 |
| 7 | 7 | min(7, low[8] = 8) | 7 |
| 6 | 6 | cạnh ngược 6–4: min(6, num[4] = 4) | 4 |
| 5 | 5 | min(5, low[6] = 4, low[7] = 7) | 4 |
| 4 | 4 | min(4, low[5] = 4) | 4 |
| 3 | 3 | cạnh ngược 3–1: min(3, num[1] = 1, low[4] = 4) | 1 |
| 2 | 2 | min(2, low[3] = 1) | 1 |
| 1 | 1 | gốc | 1 |
Bảng 1. Tính low từ dưới lên (đỉnh duyệt xong trước được tính trước). Ô xanh: low nhỏ hơn num, tức cây con có đường vòng leo lên trên.
Phần 2Cầu và đỉnh khớp trên đồ thị vô hướng
Cầu là cạnh mà xoá đi thì số thành phần liên thông tăng lên. Đỉnh khớp (khớp) là đỉnh mà xoá đi (cùng các cạnh của nó) thì số thành phần liên thông tăng lên. Với cạnh cây $u$–$c$ ($u$ là cha của $c$):
- $u$–$c$ là cầu khi và chỉ khi low[c] > num[u]: cây con gốc $c$ không có cạnh ngược nào lên tới $u$ hay cao hơn, nên cắt $u$–$c$ là nó rời ra. (Cạnh ngược không bao giờ là cầu, vì nó nằm trên một chu trình.)
- $u$ (không phải gốc) là khớp khi có ít nhất một con $c$ với low[c] ≥ num[u]: cây con của $c$ leo cao nhất cũng chỉ tới $u$, bỏ $u$ đi là nó rời khỏi phần phía trên.
- Gốc DFS là khớp khi và chỉ khi nó có từ 2 con trở lên trong cây DFS (các nhánh con không có cạnh ngang nối nhau, chỉ gặp nhau ở gốc).
Áp dụng vào Hình 1: cạnh 3–4 có low[4] = 4 > num[3] = 3 nên là cầu; 5–7 có low[7] = 7 > 5 và 7–8 có low[8] = 8 > 7 cũng là cầu. Còn 4–5 thì low[5] = 4 không lớn hơn num[4] = 4: cắt 4–5 vẫn còn đường 4–6–5. Về khớp: 3 (vì low[4] = 4 ≥ 3), 4 (low[5] = 4 ≥ 4), 5 (low[7] = 7 ≥ 5), 7 (low[8] = 8 ≥ 7). Gốc 1 chỉ có một con là 2 nên không là khớp.
Hình 2. Ba cầu (đỏ đậm) và bốn khớp (viền đỏ) của đồ thị ở Hình 1. Để ý 4 là khớp dù cạnh 4–5 không phải cầu: điều kiện khớp dùng ≥, điều kiện cầu dùng >.
Đọc tới đây chắc em vẫn thấy hơi rối: low thay đổi lúc nào, khi nào thì so sánh? Em bấm Tiếp từng bước trong mô phỏng dưới đây, xem num/low của từng đỉnh được điền dần, rồi thử thêm một cạnh (ví dụ 2 4) để thấy cầu 3–4 biến mất:
Xem code C++ / Python: tìm cầu và khớp bằng num/low (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n, m, timer_ = 0;
int num[100005], low[100005], child[100005];
bool isCut[100005];
vector<pair<int, int>> adj[100005]; // (đỉnh kề, chỉ số cạnh)
vector<pair<int, int>> bridges;
void dfs(int u, int pe){ // pe: chỉ số cạnh cha (-1 nếu u là gốc)
num[u] = low[u] = ++timer_;
for(auto &e : adj[u]){ // e = (đỉnh kề, chỉ số cạnh)
int v = e.first;
if(e.second == pe) continue; // bỏ đúng cạnh cha, KHÔNG bỏ theo đỉnh
if(num[v]){ // cạnh ngược
low[u] = min(low[u], num[v]);
} else { // cạnh cây
child[u]++;
dfs(v, e.second);
low[u] = min(low[u], low[v]);
if(low[v] > num[u]) bridges.push_back({min(u, v), max(u, v)});
if(pe != -1 && low[v] >= num[u]) isCut[u] = true;
}
}
if(pe == -1 && child[u] >= 2) isCut[u] = true; // gốc: khớp khi có từ 2 con
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
adj[u].push_back({v, i}); adj[v].push_back({u, i});
}
for(int u = 1; u <= n; u++) if(!num[u]) dfs(u, -1);
vector<int> cuts;
for(int u = 1; u <= n; u++) if(isCut[u]) cuts.push_back(u);
cout << cuts.size();
for(int u : cuts) cout << " " << u;
sort(bridges.begin(), bridges.end());
cout << "\n" << bridges.size() << "\n";
for(auto b : bridges) cout << b.first << " " << b.second << "\n";
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)] # (đỉnh kề, chỉ số cạnh)
for i in range(m):
u, v = int(data[2 + 2 * i]), int(data[3 + 2 * i])
adj[u].append((v, i)); adj[v].append((u, i))
num = [0] * (n + 1); low = [0] * (n + 1)
pe = [-1] * (n + 1) # chỉ số cạnh cha
par = [0] * (n + 1)
it = [0] * (n + 1) # đã xét tới cạnh thứ mấy của u
is_cut = [False] * (n + 1)
bridges = []
timer = 0
for s in range(1, n + 1):
if num[s]:
continue
timer += 1; num[s] = low[s] = timer
root_child = 0
stack = [s] # ngăn xếp thay cho đệ quy
while stack:
u = stack[-1]
if it[u] < len(adj[u]): # còn cạnh chưa xét: xét tiếp 1 cạnh
v, idx = adj[u][it[u]]
it[u] += 1
if idx == pe[u]:
continue
if num[v]: # cạnh ngược
if num[v] < low[u]:
low[u] = num[v]
else: # cạnh cây: "gọi đệ quy" = đẩy v vào
timer += 1; num[v] = low[v] = timer
pe[v] = idx; par[v] = u
stack.append(v)
else: # u xong: "trả về" cho cha
stack.pop()
if stack:
p = par[u]
if low[u] < low[p]:
low[p] = low[u]
if low[u] > num[p]:
bridges.append((min(u, p), max(u, p)))
if p == s:
root_child += 1
elif low[u] >= num[p]:
is_cut[p] = True
if root_child >= 2:
is_cut[s] = True
cuts = [u for u in range(1, n + 1) if is_cut[u]]
bridges.sort()
out = [" ".join(map(str, [len(cuts)] + cuts)), str(len(bridges))]
out += ["%d %d" % b for b in bridges]
print("\n".join(out))
main()Phần quan trọng nhất là hàm dfs. Em chạy tay từng dòng với đồ thị Hình 1, để ý mảng low thay đổi ngay sau mỗi cạnh ngược và mỗi lần quay về từ con:
2. Cạnh song song. Nhiều bạn bỏ qua cha bằng
if(v == parent) continue;. Nếu giữa $u$ và cha có hai cạnh thì cạnh thứ hai thực chất là một cạnh ngược, nhưng cách viết trên bỏ luôn nó, và cạnh đôi bị báo nhầm là cầu. Cách đúng: lưu chỉ số cạnh và chỉ bỏ đúng cạnh vừa đi xuống (id == pe). Với khớp thì cạnh song song không ảnh hưởng, nhưng cứ dùng chỉ số cạnh cho chắc.DFS trong Python: vì sao phải khử đệ quy? Python mặc định chỉ cho đệ quy sâu khoảng 1000 tầng. Đồ thị là một đường thẳng $10^5$ đỉnh thì DFS phải sâu $10^5$ tầng, chương trình chết với lỗi RecursionError. Tăng sys.setrecursionlimit thôi chưa đủ: ngăn xếp thật của hệ điều hành vẫn bị tràn và chương trình bị “crash” không báo lỗi. Có hai cách chữa. Cách thứ nhất: tăng giới hạn và chạy trong một luồng có ngăn xếp lớn:
import sys, threading
def main():
sys.setrecursionlimit(1 << 20) # cho phép đệ quy rất sâu...
# ... đọc dữ liệu, gọi dfs(u) đệ quy như bản C++ ...
threading.stack_size(1 << 27) # ...và cấp cho luồng mới 128 MB ngăn xếp
threading.Thread(target=main).start()Cách này tiện nhưng chậm và một số máy chấm không cho tạo luồng. Cách thứ hai, an toàn nhất, là tự quản lý ngăn xếp như code Python ở trên. Mẹo nằm ở mảng it[u]: “đỉnh u đã xét tới cạnh thứ mấy”. Mỗi vòng lặp chỉ nhìn đỉnh trên cùng của ngăn xếp:
- nếu nó còn cạnh chưa xét thì xét một cạnh; gặp đỉnh chưa thăm thì đẩy vào (tương đương gọi
dfs(v)); - nếu đã hết cạnh thì bật ra và cập nhật cho cha
low[cha] = min(low[cha], low[u])(tương đương trả về từ lời gọi đệ quy).
dfs tìm cầu ở trên đã tràn ngăn xếp khi đồ thị là một đường thẳng $10^5$ đỉnh (thầy đã thử). Khi không chắc máy chấm, em khử đệ quy theo đúng khuôn này cho cả C++.Phần 3Thành phần liên thông mạnh: thuật toán Tarjan
Trên đồ thị có hướng, hai đỉnh $u$, $v$ thuộc cùng một thành phần liên thông mạnh (TPLT mạnh, tiếng Anh SCC) nếu đi được từ $u$ tới $v$ và từ $v$ về $u$. Mỗi đỉnh thuộc đúng một TPLT mạnh; một đỉnh không nằm trên chu trình nào thì tự nó là một TPLT mạnh. Hình 3 có bốn thành phần: {1, 2, 3}, {4, 5, 6}, {7}, {8}. Đỉnh 7 đi được tới 8 nhưng 8 không quay về được, nên chúng ở hai thành phần khác nhau.
Hình 3. Bốn TPLT mạnh tô bốn màu. Cung xám nét đứt nối hai thành phần khác nhau. Số cạnh đỉnh là num/low khi Tarjan chạy từ đỉnh 1.
Tarjan vẫn dùng num/low, thêm một ngăn xếp st chứa các đỉnh “đã thăm nhưng chưa được xếp vào thành phần nào”:
- Thăm $u$: gán
num[u] = low[u] = ++timervà đẩy $u$ vàost. - Cung $u \to v$ với $v$ chưa thăm: gọi
dfs(v)rồilow[u] = min(low[u], low[v]). - Cung $u \to v$ với $v$ còn trong ngăn xếp: $v$ là tổ tiên hoặc cùng thành phần đang dở dang, đi tới $v$ là quay về được phía trên, nên
low[u] = min(low[u], num[v]). - Cung $u \to v$ với $v$ đã thăm và đã rời ngăn xếp: $v$ thuộc một thành phần đã chốt xong, từ đó không có đường về $u$. Bỏ qua.
- Duyệt xong $u$ mà low[u] = num[u]: $u$ là đỉnh thăm sớm nhất (“gốc”) của thành phần của nó. Bật khỏi ngăn xếp cho tới khi gặp $u$: tất cả các đỉnh bật ra là trọn một TPLT mạnh.
Vì sao các đỉnh nằm phía trên $u$ trong ngăn xếp đúng là thành phần của $u$? Chúng đều là con cháu của $u$ được thăm sau $u$. Đỉnh nào trong số đó thuộc thành phần khác thì thành phần ấy đã có gốc riêng (low = num) và đã bị bật ra trước rồi. Những đỉnh còn lại thì low < num, tức chúng quay lên được tới $u$, mà $u$ cũng đi xuống được tới chúng.
Thứ tự bật ra trên Hình 3 là {8}, {7}, {4, 5, 6}, {1, 2, 3}: thành phần “cuối dòng” bật ra trước. Mô phỏng dưới đây vẽ cả ngăn xếp: em để ý đỉnh 6 có cung tới 7 nhưng 7 đã rời ngăn xếp nên low[6] không bị kéo xuống. Thử đổi đồ thị, ví dụ thêm cung 8 1 để cả đồ thị thành một khối:
Xem code C++ / Python: thuật toán Tarjan tìm thành phần liên thông mạnh (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n, m, timer_ = 0, cnt = 0;
int num[100005], low[100005], comp[100005];
bool onStk[100005];
vector<int> adj[100005];
vector<int> st; // ngăn xếp của Tarjan
void dfs(int u){
num[u] = low[u] = ++timer_;
st.push_back(u); onStk[u] = true;
for(int v : adj[u]){
if(!num[v]){ // cung cây
dfs(v);
low[u] = min(low[u], low[v]);
} else if(onStk[v]){ // v còn trong ngăn xếp: cùng vòng
low[u] = min(low[u], num[v]);
} // v đã thuộc TPLT khác: bỏ qua
}
if(low[u] == num[u]){ // u là gốc của một TPLT mạnh
cnt++;
while(true){
int v = st.back(); st.pop_back();
onStk[v] = false; comp[v] = cnt;
if(v == u) break;
}
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
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(!num[u]) dfs(u);
vector<vector<int>> g(cnt + 1);
for(int u = 1; u <= n; u++) g[comp[u]].push_back(u); // u tăng dần nên mỗi nhóm đã tăng
sort(g.begin() + 1, g.end()); // xếp các nhóm theo đỉnh nhỏ nhất
cout << cnt << "\n";
for(int c = 1; c <= cnt; c++){
for(int u : g[c]) cout << u << " ";
cout << "\n";
}
return 0;
}import sys
def tarjan(n, adj):
"""Trả về (cnt, comp): comp[u] = số hiệu TPLT mạnh của u (1..cnt),
đánh số theo thứ tự bật ra khỏi ngăn xếp (= ngược thứ tự topo)."""
num = [0] * (n + 1); low = [0] * (n + 1); comp = [0] * (n + 1)
on = [False] * (n + 1); it = [0] * (n + 1)
stk = []; timer = 0; cnt = 0
for s in range(1, n + 1):
if num[s]:
continue
timer += 1; num[s] = low[s] = timer
stk.append(s); on[s] = True
call = [s] # ngăn xếp lời gọi tự quản lý
while call:
u = call[-1]
if it[u] < len(adj[u]):
v = adj[u][it[u]]; it[u] += 1
if not num[v]: # cung cây: "gọi" dfs(v)
timer += 1; num[v] = low[v] = timer
stk.append(v); on[v] = True
call.append(v)
elif on[v] and num[v] < low[u]: # v còn trong ngăn xếp
low[u] = num[v]
else: # u xong: "trả về"
call.pop()
if call and low[u] < low[call[-1]]:
low[call[-1]] = low[u]
if low[u] == num[u]: # bật một TPLT mạnh
cnt += 1
while True:
v = stk.pop(); on[v] = False; comp[v] = cnt
if v == u:
break
return cnt, comp
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]))
cnt, comp = tarjan(n, adj)
groups = [[] for _ in range(cnt + 1)]
for u in range(1, n + 1):
groups[comp[u]].append(u)
out = [str(cnt)] + [" ".join(map(str, g)) for g in sorted(groups[1:])]
print("\n".join(out))
main()Khung chạy tay dưới đây cho em thấy từng dòng của hàm dfs trong Tarjan, kèm nội dung ngăn xếp st và mảng comp (số hiệu thành phần):
onStk[v] là lỗi phổ biến nhất: khi đó cung 6→7 ở Hình 3 sẽ kéo low[6] xuống 4 và gộp nhầm.Phần 4Kosaraju: hai lần DFS, và đồ thị nén là một DAG
Kosaraju là cách thứ hai, dễ hiểu hơn và không cần low:
- Lượt 1: DFS trên đồ thị $G$, mỗi đỉnh duyệt xong thì ghi vào danh sách
order(thứ tự xong). - Đảo chiều mọi cung, được đồ thị $G^T$.
- Lượt 2: lấy các đỉnh theo thứ tự xong giảm dần; gặp đỉnh chưa được gán thì DFS trên $G^T$ từ nó, mọi đỉnh tới được (chưa gán) tạo thành một TPLT mạnh.
Vì sao đúng? Đỉnh xong muộn nhất thuộc một thành phần nguồn (không có cung từ thành phần khác đi vào). Trên $G^T$, các cung ra khỏi thành phần nguồn đều đã bị đảo thành cung đi vào, nên DFS từ đó chỉ lan trong đúng thành phần của nó. Gán xong thì coi như xoá thành phần ấy, đỉnh xong muộn nhất còn lại lại thuộc một thành phần nguồn của phần còn lại, cứ thế tiếp tục.
Em xem hai lượt chạy trên cùng đồ thị Hình 3. Ở lượt 2, hình được vẽ với mọi cung đã đảo chiều:
Xem code C++ / Python: thuật toán Kosaraju hai lần DFS (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int n, m, cnt = 0;
vector<int> adj[100005], radj[100005], order_;
bool vis[100005];
int comp[100005];
void dfs1(int u){ // lượt 1: trên G, ghi thứ tự xong
vis[u] = true;
for(int v : adj[u]) if(!vis[v]) dfs1(v);
order_.push_back(u);
}
void dfs2(int u){ // lượt 2: trên G đảo, gom một TPLT
comp[u] = cnt;
for(int v : radj[u]) if(!comp[v]) dfs2(v);
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
radj[v].push_back(u); // cung đảo chiều
}
for(int u = 1; u <= n; u++) if(!vis[u]) dfs1(u);
for(int i = n - 1; i >= 0; i--){ // xét theo thứ tự xong giảm dần
int u = order_[i];
if(!comp[u]){ cnt++; dfs2(u); }
}
vector<vector<int>> g(cnt + 1);
for(int u = 1; u <= n; u++) g[comp[u]].push_back(u);
sort(g.begin() + 1, g.end());
cout << cnt << "\n";
for(int c = 1; c <= cnt; c++){
for(int u : g[c]) cout << u << " ";
cout << "\n";
}
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)]
radj = [[] for _ in range(n + 1)]
for i in range(m):
u, v = int(data[2 + 2 * i]), int(data[3 + 2 * i])
adj[u].append(v)
radj[v].append(u) # cung đảo chiều
# lượt 1: DFS không đệ quy trên G, ghi thứ tự xong
order = []
vis = [False] * (n + 1)
it = [0] * (n + 1)
for s in range(1, n + 1):
if vis[s]:
continue
vis[s] = True
stack = [s]
while stack:
u = stack[-1]
if it[u] < len(adj[u]):
v = adj[u][it[u]]; it[u] += 1
if not vis[v]:
vis[v] = True
stack.append(v)
else:
stack.pop()
order.append(u) # u xong
# lượt 2: trên G đảo, theo thứ tự xong giảm dần
comp = [0] * (n + 1)
cnt = 0
for s in reversed(order):
if comp[s]:
continue
cnt += 1
comp[s] = cnt
stack = [s]
while stack: # lượt 2 chỉ cần biết ai tới được
u = stack.pop()
for v in radj[u]:
if not comp[v]:
comp[v] = cnt
stack.append(v)
groups = [[] for _ in range(cnt + 1)]
for u in range(1, n + 1):
groups[comp[u]].append(u)
out = [str(cnt)] + [" ".join(map(str, g)) for g in sorted(groups[1:])]
print("\n".join(out))
main()| Tiêu chí | Tarjan | Kosaraju |
|---|---|---|
| Số lần DFS | 1 | 2 (thêm đồ thị đảo) |
| Bộ nhớ thêm | num, low, ngăn xếp | danh sách kề đảo chiều |
| Thứ tự thành phần tìm được | ngược thứ tự topo | đúng thứ tự topo |
| Dễ code sai | quên onStk | ít chỗ sai |
| Độ phức tạp | $O(n + m)$ | $O(n + m)$ |
Bảng 2. Hai thuật toán cho cùng các thành phần, chỉ khác thứ tự đánh số.
Đồ thị nén. Gom mỗi TPLT mạnh thành một đỉnh, giữ lại các cung nối hai thành phần khác nhau, ta được đồ thị nén (condensation). Đồ thị nén luôn là DAG: nếu có chu trình giữa các thành phần thì đi vòng được qua chúng, tức chúng phải gộp thành một thành phần, vô lý. Thế là mọi kỹ thuật của bài 35 (sắp xếp topo, quy hoạch động trên DAG, đường đi dài nhất) dùng được cho mọi đồ thị có hướng, kể cả có chu trình.
Hình 4. Đồ thị nén của Hình 3. A là thành phần nguồn duy nhất, D là thành phần đích duy nhất.
Phần 5Ứng dụng: thêm cung, chọn đỉnh xuất phát, 2-SAT
Hầu hết bài TPLT mạnh trong đề thi đều đi theo một kịch bản: nén đồ thị, rồi đếm hay quy hoạch động trên DAG nén. Gọi $s$ là số thành phần nguồn (bán bậc vào bằng 0) và $t$ là số thành phần đích (bán bậc ra bằng 0) của đồ thị nén:
| Câu hỏi | Đáp án | Vì sao |
|---|---|---|
| Ít đỉnh xuất phát nhất để đi tới mọi đỉnh | $s$ | mỗi thành phần nguồn không ai đi vào được, bắt buộc chọn một đỉnh trong nó; chọn đủ $s$ đỉnh đó là tới được tất cả |
| Thêm ít cung nhất để cả đồ thị liên thông mạnh | $\max(s, t)$, riêng 1 thành phần thì 0 | mỗi nguồn cần thêm một cung vào, mỗi đích cần thêm một cung ra; nối vòng các đích về các nguồn là đủ |
| Đi từ $u$, được thăm tối đa bao nhiêu đỉnh / nhặt tối đa bao nhiêu điểm | QHĐ trên DAG nén | vào một thành phần là đi hết được cả thành phần đó |
| Có thể định hướng mọi cạnh vô hướng để được đồ thị liên thông mạnh? | được khi và chỉ khi liên thông và không có cầu | định hướng cạnh cây đi xuống, cạnh ngược đi lên |
Bảng 3. Các dạng câu hỏi hay gặp. Với Hình 4: $s = 1$ (A), $t = 1$ (D), nên chỉ cần xuất phát từ 1 đỉnh của A và thêm 1 cung, ví dụ 8 → 1.
Giới thiệu 2-SAT. Có $n$ biến đúng/sai và nhiều điều kiện dạng “$a$ hoặc $b$” (mỗi vế là một biến hoặc phủ định của nó). Có gán được giá trị để mọi điều kiện đều đúng không? Mỗi điều kiện $a \lor b$ tương đương hai phép kéo theo: “nếu không $a$ thì phải $b$” và “nếu không $b$ thì phải $a$”. Lập đồ thị $2n$ đỉnh (mỗi biến có đỉnh “$x$ đúng” và “$x$ sai”), mỗi điều kiện thêm hai cung $\lnot a \to b$, $\lnot b \to a$. Kết luận rất gọn:
Vô nghiệm khi và chỉ khi có biến $x$ mà “$x$ đúng” và “$x$ sai” cùng một TPLT mạnh.
Vì khi đó $x \Rightarrow \lnot x$ và $\lnot x \Rightarrow x$, gán kiểu gì cũng mâu thuẫn. Ngược lại, nếu không có biến nào như vậy thì luôn có nghiệm: với Tarjan, gán $x$ đúng khi comp[x đúng] < comp[x sai] (chọn vế nằm “sau” trong thứ tự topo). Bài toán chọn phương án thoả nhiều ràng buộc đôi một như xếp lịch, chọn đội hình “A đi thì B không đi” đều quy về 2-SAT, em làm thử ở bài tập 8.
• “Đi qua đi lại được”, “đường một chiều”, “lan truyền”, “chu trình trên đồ thị có hướng” → TPLT mạnh rồi nén thành DAG.
• Đồ thị vô hướng mà chỉ hỏi “có đi được tới nhau không” thì DSU hoặc BFS ở bài 30, bài 21 là đủ, không cần num/low.
• Python: luôn viết DFS không đệ quy khi $n$ lớn.
- Covid (ICTU P58) (Trung bình)
- Lá Bài (LABAI) (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ó)
Bài tậpLuyện cầu, khớp và thành phần liên thông mạnh
Mạng giao thông có $n$ thành phố và $m$ con đường hai chiều ($1 \le n \le 10^5$, $0 \le m \le 2 \cdot 10^5$). Giữa hai thành phố có thể có nhiều con đường, không có đường nối một thành phố với chính nó. Một con đường gọi là huyết mạch nếu nó bị sập thì có hai thành phố đang đi được tới nhau trở thành không đi được. Đếm số đường huyết mạch.
Input: dòng đầu $n, m$; $m$ dòng sau mỗi dòng hai số $u, v$. Output: số đường huyết mạch.
6 7
1 2
2 3
3 1
3 4
4 5
4 5
5 62📝 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 num[100005], low[100005], timer_ = 0, cnt = 0;
vector<pair<int, int>> adj[100005];
void dfs(int u, int pe){
num[u] = low[u] = ++timer_;
for(auto e : adj[u]){
int v = e.first, id = e.second;
if(id == pe) continue; // bỏ đúng cạnh cha theo chỉ số
if(num[v]) low[u] = min(low[u], num[v]);
else {
dfs(v, id);
low[u] = min(low[u], low[v]);
if(low[v] > num[u]) cnt++;
}
}
}
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, i}); adj[v].push_back({u, i});
}
for(int u = 1; u <= n; u++) if(!num[u]) dfs(u, -1);
cout << cnt;
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):
u, v = int(data[2 + 2 * i]), int(data[3 + 2 * i])
adj[u].append((v, i)); adj[v].append((u, i))
num = [0] * (n + 1); low = [0] * (n + 1)
pe = [-1] * (n + 1); par = [0] * (n + 1); it = [0] * (n + 1)
timer = cnt = 0
for s in range(1, n + 1):
if num[s]:
continue
timer += 1; num[s] = low[s] = timer
stack = [s]
while stack:
u = stack[-1]
if it[u] < len(adj[u]):
v, idx = adj[u][it[u]]; it[u] += 1
if idx == pe[u]:
continue
if num[v]:
low[u] = min(low[u], num[v])
else:
timer += 1; num[v] = low[v] = timer
pe[v] = idx; par[v] = u
stack.append(v)
else:
stack.pop()
if stack:
p = par[u]
low[p] = min(low[p], low[u])
if low[u] > num[p]:
cnt += 1
print(cnt)
main()Có $n$ người ($1 \le n \le 2 \cdot 10^5$) và $m$ quan hệ “$u$ nhắn tin được cho $v$” ($0 \le m \le 2 \cdot 10^5$, có hướng). Một câu lạc bộ là một nhóm lớn nhất có thể mà hai người bất kỳ trong nhóm đều chuyển tin được cho nhau (có thể qua người trung gian). Mỗi người thuộc đúng một câu lạc bộ. In ra số câu lạc bộ và số thành viên của câu lạc bộ đông nhất.
8 8
1 2
2 1
2 3
3 4
4 5
5 3
6 7
7 64 3📝 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 num[200005], low[200005], comp[200005], timer_ = 0, cnt = 0;
bool onStk[200005];
vector<int> adj[200005], st;
void dfs(int u){
num[u] = low[u] = ++timer_;
st.push_back(u); onStk[u] = true;
for(int v : adj[u]){
if(!num[v]){ dfs(v); low[u] = min(low[u], low[v]); }
else if(onStk[v]) low[u] = min(low[u], num[v]);
}
if(low[u] == num[u]){
cnt++;
while(true){
int v = st.back(); st.pop_back();
onStk[v] = false; comp[v] = cnt;
if(v == u) break;
}
}
}
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(!num[u]) dfs(u);
vector<int> sz(cnt + 1, 0);
for(int u = 1; u <= n; u++) sz[comp[u]]++;
cout << cnt << " " << *max_element(sz.begin() + 1, sz.end());
return 0;
}import sys
def tarjan(n, adj): # Tarjan không đệ quy, như phần 3
num = [0] * (n + 1); low = [0] * (n + 1); comp = [0] * (n + 1)
on = [False] * (n + 1); it = [0] * (n + 1)
stk = []; timer = cnt = 0
for s in range(1, n + 1):
if num[s]:
continue
timer += 1; num[s] = low[s] = timer; stk.append(s); on[s] = True
call = [s]
while call:
u = call[-1]
if it[u] < len(adj[u]):
v = adj[u][it[u]]; it[u] += 1
if not num[v]:
timer += 1; num[v] = low[v] = timer
stk.append(v); on[v] = True; call.append(v)
elif on[v] and num[v] < low[u]:
low[u] = num[v]
else:
call.pop()
if call and low[u] < low[call[-1]]:
low[call[-1]] = low[u]
if low[u] == num[u]:
cnt += 1
while True:
v = stk.pop(); on[v] = False; comp[v] = cnt
if v == u:
break
return cnt, comp
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]))
cnt, comp = tarjan(n, adj)
sz = [0] * (cnt + 1)
for u in range(1, n + 1):
sz[comp[u]] += 1
print(cnt, max(sz))
main()Mạng điện gồm $n$ trạm ($2 \le n \le 10^5$) và $m$ đường dây hai chiều ($n - 1 \le m \le 2 \cdot 10^5$), mạng liên thông, có thể có đường dây lặp. Nếu một trạm bị hỏng (cùng mọi đường dây nối với nó) thì $n - 1$ trạm còn lại bị chia thành mấy vùng liên thông? Tìm trạm hỏng gây ra nhiều vùng nhất và số vùng đó. Nhiều trạm như nhau thì in trạm có số hiệu nhỏ nhất.
7 7
1 2
1 3
2 3
3 4
4 5
4 6
6 74 3📝 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 num[100005], low[100005], piece[100005], timer_ = 0;
vector<int> adj[100005];
void dfs(int u, int p){
num[u] = low[u] = ++timer_;
bool parentSkipped = false;
for(int v : adj[u]){
if(v == p && !parentSkipped){ parentSkipped = true; continue; } // bỏ 1 cạnh cha
if(num[v]) low[u] = min(low[u], num[v]);
else {
dfs(v, u);
low[u] = min(low[u], low[v]);
if(low[v] >= num[u]) piece[u]++; // cây con của v tách ra
}
}
if(p != 0) piece[u]++; // + phần phía trên (chứa cha)
}
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); adj[v].push_back(u);
}
dfs(1, 0);
int best = 1;
for(int u = 2; u <= n; u++) if(piece[u] > piece[best]) best = u;
cout << best << " " << piece[best];
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):
u, v = int(data[2 + 2 * i]), int(data[3 + 2 * i])
adj[u].append((v, i)); adj[v].append((u, i))
num = [0] * (n + 1); low = [0] * (n + 1); piece = [0] * (n + 1)
pe = [-1] * (n + 1); par = [0] * (n + 1); it = [0] * (n + 1)
timer = 1; num[1] = low[1] = 1
stack = [1]
while stack:
u = stack[-1]
if it[u] < len(adj[u]):
v, idx = adj[u][it[u]]; it[u] += 1
if idx == pe[u]:
continue
if num[v]:
low[u] = min(low[u], num[v])
else:
timer += 1; num[v] = low[v] = timer
pe[v] = idx; par[v] = u
stack.append(v)
else:
stack.pop()
if u != 1:
piece[u] += 1 # phần phía trên (chứa cha)
p = par[u]
low[p] = min(low[p], low[u])
if low[u] >= num[p]:
piece[p] += 1 # cây con của u tách ra
best = 1
for u in range(2, n + 1):
if piece[u] > piece[best]:
best = u
print(best, piece[best])
main()Có $n$ học sinh ($1 \le n \le 2 \cdot 10^5$) và $m$ quan hệ “$u$ nghe được tin thì sẽ kể cho $v$” ($0 \le m \le 2 \cdot 10^5$). Thầy muốn báo tin trực tiếp cho ít học sinh nhất sao cho cuối cùng cả lớp đều biết. Hỏi cần báo cho mấy bạn?
6 6
1 2
2 3
3 1
4 3
5 6
6 52📝 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 num[200005], low[200005], comp[200005], timer_ = 0, cnt = 0;
bool onStk[200005];
vector<int> adj[200005], st;
void dfs(int u){
num[u] = low[u] = ++timer_;
st.push_back(u); onStk[u] = true;
for(int v : adj[u]){
if(!num[v]){ dfs(v); low[u] = min(low[u], low[v]); }
else if(onStk[v]) low[u] = min(low[u], num[v]);
}
if(low[u] == num[u]){
cnt++;
while(true){
int v = st.back(); st.pop_back();
onStk[v] = false; comp[v] = cnt;
if(v == u) break;
}
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<pair<int, int>> E(m);
for(auto &e : E){
cin >> e.first >> e.second;
adj[e.first].push_back(e.second);
}
for(int u = 1; u <= n; u++) if(!num[u]) dfs(u);
vector<int> indeg(cnt + 1, 0);
for(auto e : E)
if(comp[e.first] != comp[e.second]) indeg[comp[e.second]]++;
int ans = 0;
for(int c = 1; c <= cnt; c++) if(indeg[c] == 0) ans++;
cout << ans;
return 0;
}import sys
def tarjan(n, adj): # Tarjan không đệ quy, như phần 3
num = [0] * (n + 1); low = [0] * (n + 1); comp = [0] * (n + 1)
on = [False] * (n + 1); it = [0] * (n + 1)
stk = []; timer = cnt = 0
for s in range(1, n + 1):
if num[s]:
continue
timer += 1; num[s] = low[s] = timer; stk.append(s); on[s] = True
call = [s]
while call:
u = call[-1]
if it[u] < len(adj[u]):
v = adj[u][it[u]]; it[u] += 1
if not num[v]:
timer += 1; num[v] = low[v] = timer
stk.append(v); on[v] = True; call.append(v)
elif on[v] and num[v] < low[u]:
low[u] = num[v]
else:
call.pop()
if call and low[u] < low[call[-1]]:
low[call[-1]] = low[u]
if low[u] == num[u]:
cnt += 1
while True:
v = stk.pop(); on[v] = False; comp[v] = cnt
if v == u:
break
return cnt, comp
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
E = []
for i in range(m):
u, v = int(data[2 + 2 * i]), int(data[3 + 2 * i])
adj[u].append(v); E.append((u, v))
cnt, comp = tarjan(n, adj)
indeg = [0] * (cnt + 1)
for u, v in E:
if comp[u] != comp[v]:
indeg[comp[v]] += 1
print(sum(1 for c in range(1, cnt + 1) if indeg[c] == 0))
main()Thành phố có $n$ nút giao ($1 \le n \le 2 \cdot 10^5$) và $m$ đường một chiều ($0 \le m \le 2 \cdot 10^5$). Hỏi cần xây thêm ít nhất bao nhiêu đường một chiều để từ mọi nút giao đi được tới mọi nút giao khác?
5 5
1 2
2 3
3 1
3 4
3 52📝 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 num[200005], low[200005], comp[200005], timer_ = 0, cnt = 0;
bool onStk[200005];
vector<int> adj[200005], st;
void dfs(int u){
num[u] = low[u] = ++timer_;
st.push_back(u); onStk[u] = true;
for(int v : adj[u]){
if(!num[v]){ dfs(v); low[u] = min(low[u], low[v]); }
else if(onStk[v]) low[u] = min(low[u], num[v]);
}
if(low[u] == num[u]){
cnt++;
while(true){
int v = st.back(); st.pop_back();
onStk[v] = false; comp[v] = cnt;
if(v == u) break;
}
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<pair<int, int>> E(m);
for(auto &e : E){
cin >> e.first >> e.second;
adj[e.first].push_back(e.second);
}
for(int u = 1; u <= n; u++) if(!num[u]) dfs(u);
if(cnt == 1){ cout << 0; return 0; } // đã liên thông mạnh
vector<int> in(cnt + 1, 0), out(cnt + 1, 0);
for(auto e : E){
int a = comp[e.first], b = comp[e.second];
if(a != b){ out[a]++; in[b]++; }
}
int src = 0, snk = 0;
for(int c = 1; c <= cnt; c++){
if(in[c] == 0) src++;
if(out[c] == 0) snk++;
}
cout << max(src, snk);
return 0;
}import sys
def tarjan(n, adj): # Tarjan không đệ quy, như phần 3
num = [0] * (n + 1); low = [0] * (n + 1); comp = [0] * (n + 1)
on = [False] * (n + 1); it = [0] * (n + 1)
stk = []; timer = cnt = 0
for s in range(1, n + 1):
if num[s]:
continue
timer += 1; num[s] = low[s] = timer; stk.append(s); on[s] = True
call = [s]
while call:
u = call[-1]
if it[u] < len(adj[u]):
v = adj[u][it[u]]; it[u] += 1
if not num[v]:
timer += 1; num[v] = low[v] = timer
stk.append(v); on[v] = True; call.append(v)
elif on[v] and num[v] < low[u]:
low[u] = num[v]
else:
call.pop()
if call and low[u] < low[call[-1]]:
low[call[-1]] = low[u]
if low[u] == num[u]:
cnt += 1
while True:
v = stk.pop(); on[v] = False; comp[v] = cnt
if v == u:
break
return cnt, comp
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
adj = [[] for _ in range(n + 1)]
E = []
for i in range(m):
u, v = int(data[2 + 2 * i]), int(data[3 + 2 * i])
adj[u].append(v); E.append((u, v))
cnt, comp = tarjan(n, adj)
if cnt == 1:
print(0)
return
din = [0] * (cnt + 1); dout = [0] * (cnt + 1)
for u, v in E:
a, b = comp[u], comp[v]
if a != b:
dout[a] += 1; din[b] += 1
src = sum(1 for c in range(1, cnt + 1) if din[c] == 0)
snk = sum(1 for c in range(1, cnt + 1) if dout[c] == 0)
print(max(src, snk))
main()Mạng $n$ thành phố ($2 \le n \le 10^5$), $m$ đường hai chiều ($n - 1 \le m \le 2 \cdot 10^5$), liên thông, có thể có đường lặp. Nếu một con đường bị sập, gọi thiệt hại là số cặp thành phố (không kể thứ tự) không còn đi được tới nhau. Tìm thiệt hại lớn nhất khi sập đúng một con đường.
6 6
1 2
2 3
3 1
3 4
4 5
4 69📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
sz[c] đỉnh, phần kia có $n - sz[c]$ đỉnh, thiệt hại $sz[c] \cdot (n - sz[c])$. Tính sz ngay trong DFS num/low. Kết quả có thể tới $2{,}5 \cdot 10^9$ nên dùng long long. Ví dụ: sập 3–4 tách {1, 2, 3} khỏi {4, 5, 6}: $3 \cdot 3 = 9$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, m, num[100005], low[100005], sz[100005], timer_ = 0;
vector<pair<int, int>> adj[100005];
long long best = 0;
void dfs(int u, int pe){
num[u] = low[u] = ++timer_;
sz[u] = 1;
for(auto e : adj[u]){
int v = e.first, id = e.second;
if(id == pe) continue;
if(num[v]) low[u] = min(low[u], num[v]);
else {
dfs(v, id);
sz[u] += sz[v];
low[u] = min(low[u], low[v]);
if(low[v] > num[u]) // cắt cầu u-v: sz[v] đỉnh tách khỏi n - sz[v] đỉnh
best = max(best, 1LL * sz[v] * (n - sz[v]));
}
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
adj[u].push_back({v, i}); adj[v].push_back({u, i});
}
dfs(1, -1);
cout << best;
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):
u, v = int(data[2 + 2 * i]), int(data[3 + 2 * i])
adj[u].append((v, i)); adj[v].append((u, i))
num = [0] * (n + 1); low = [0] * (n + 1); sz = [1] * (n + 1)
pe = [-1] * (n + 1); par = [0] * (n + 1); it = [0] * (n + 1)
timer = 1; num[1] = low[1] = 1
best = 0
stack = [1]
while stack:
u = stack[-1]
if it[u] < len(adj[u]):
v, idx = adj[u][it[u]]; it[u] += 1
if idx == pe[u]:
continue
if num[v]:
low[u] = min(low[u], num[v])
else:
timer += 1; num[v] = low[v] = timer
pe[v] = idx; par[v] = u
stack.append(v)
else:
stack.pop()
if stack:
p = par[u]
sz[p] += sz[u]
low[p] = min(low[p], low[u])
if low[u] > num[p]:
best = max(best, sz[u] * (n - sz[u]))
print(best)
main()Có $n$ hang ($1 \le n \le 10^5$), hang $i$ chứa $a_i$ thỏi vàng ($0 \le a_i \le 10^9$), và $m$ đường hầm một chiều ($0 \le m \le 2 \cdot 10^5$). Em xuất phát ở hang 1, đi tuỳ ý theo đường hầm, được đi lại một hang nhiều lần nhưng vàng mỗi hang chỉ nhặt được một lần. Hỏi nhặt được nhiều nhất bao nhiêu thỏi vàng?
Input: dòng đầu $n, m$; dòng hai gồm $a_1 \ldots a_n$; $m$ dòng sau là các đường hầm $u \to v$.
6 7
1 2 3 4 5 10
1 2
2 3
3 1
3 4
4 5
5 4
2 616📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
best[c] với $c$ tăng dần là xong. Ví dụ: {1, 2, 3} có 6 thỏi, rồi đi sang {6} được thêm 10, tổng 16 (đi sang {4, 5} chỉ được 9).Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int num[200005], low[200005], comp[200005], timer_ = 0, cnt = 0;
bool onStk[200005];
vector<int> adj[200005], st;
void dfs(int u){
num[u] = low[u] = ++timer_;
st.push_back(u); onStk[u] = true;
for(int v : adj[u]){
if(!num[v]){ dfs(v); low[u] = min(low[u], low[v]); }
else if(onStk[v]) low[u] = min(low[u], num[v]);
}
if(low[u] == num[u]){
cnt++;
while(true){
int v = st.back(); st.pop_back();
onStk[v] = false; comp[v] = cnt;
if(v == u) break;
}
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<long long> a(n + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
vector<pair<int, int>> E(m);
for(auto &e : E){
cin >> e.first >> e.second;
adj[e.first].push_back(e.second);
}
for(int u = 1; u <= n; u++) if(!num[u]) dfs(u);
vector<long long> val(cnt + 1, 0), best(cnt + 1, 0);
vector<vector<int>> nxt(cnt + 1);
for(int u = 1; u <= n; u++) val[comp[u]] += a[u];
for(auto e : E){
int x = comp[e.first], y = comp[e.second];
if(x != y) nxt[x].push_back(y); // luôn có y < x
}
for(int c = 1; c <= cnt; c++){ // số hiệu tăng dần = ngược thứ tự topo
long long add = 0;
for(int d : nxt[c]) add = max(add, best[d]);
best[c] = val[c] + add;
}
cout << best[comp[1]];
return 0;
}import sys
def tarjan(n, adj): # Tarjan không đệ quy, như phần 3
num = [0] * (n + 1); low = [0] * (n + 1); comp = [0] * (n + 1)
on = [False] * (n + 1); it = [0] * (n + 1)
stk = []; timer = cnt = 0
for s in range(1, n + 1):
if num[s]:
continue
timer += 1; num[s] = low[s] = timer; stk.append(s); on[s] = True
call = [s]
while call:
u = call[-1]
if it[u] < len(adj[u]):
v = adj[u][it[u]]; it[u] += 1
if not num[v]:
timer += 1; num[v] = low[v] = timer
stk.append(v); on[v] = True; call.append(v)
elif on[v] and num[v] < low[u]:
low[u] = num[v]
else:
call.pop()
if call and low[u] < low[call[-1]]:
low[call[-1]] = low[u]
if low[u] == num[u]:
cnt += 1
while True:
v = stk.pop(); on[v] = False; comp[v] = cnt
if v == u:
break
return cnt, comp
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
adj = [[] for _ in range(n + 1)]
E = []
pos = 2 + n
for i in range(m):
u, v = int(data[pos + 2 * i]), int(data[pos + 2 * i + 1])
adj[u].append(v); E.append((u, v))
cnt, comp = tarjan(n, adj)
val = [0] * (cnt + 1)
for u in range(1, n + 1):
val[comp[u]] += a[u]
nxt = [[] for _ in range(cnt + 1)]
for u, v in E:
if comp[u] != comp[v]:
nxt[comp[u]].append(comp[v]) # luôn sang số hiệu nhỏ hơn
best = [0] * (cnt + 1)
for c in range(1, cnt + 1): # ngược thứ tự topo
best[c] = val[c] + max((best[d] for d in nxt[c]), default=0)
print(best[comp[1]])
main()Có $n$ bạn ($1 \le n \le 10^5$), mỗi bạn hoặc được chọn hoặc không. Có $m$ yêu cầu ($1 \le m \le 2 \cdot 10^5$), mỗi yêu cầu cho hai số nguyên $a, b$ ($1 \le |a|, |b| \le n$): số dương $x$ nghĩa là “bạn $x$ được chọn”, số âm $-x$ nghĩa là “bạn $x$ không được chọn”, và yêu cầu đòi ít nhất một trong hai điều đó đúng. In YES nếu có cách chọn thoả mọi yêu cầu, ngược lại in NO.
3 4
1 2
-1 2
-2 3
-1 -3YES📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
-2 -3 thì thành vô nghiệm.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int num[200005], low[200005], comp[200005], timer_ = 0, cnt = 0;
bool onStk[200005];
vector<int> adj[200005], st;
void dfs(int u){
num[u] = low[u] = ++timer_;
st.push_back(u); onStk[u] = true;
for(int v : adj[u]){
if(!num[v]){ dfs(v); low[u] = min(low[u], low[v]); }
else if(onStk[v]) low[u] = min(low[u], num[v]);
}
if(low[u] == num[u]){
cnt++;
while(true){
int v = st.back(); st.pop_back();
onStk[v] = false; comp[v] = cnt;
if(v == u) break;
}
}
}
int n, m;
int node(int x){ // literal x > 0: x đúng; x < 0: x sai
return x > 0 ? 2 * x : 2 * (-x) + 1;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b; // mệnh đề (a hoặc b)
adj[node(-a)].push_back(node(b)); // không a thì phải b
adj[node(-b)].push_back(node(a)); // không b thì phải a
}
for(int u = 2; u <= 2 * n + 1; u++) if(!num[u]) dfs(u);
for(int x = 1; x <= n; x++)
if(comp[2 * x] == comp[2 * x + 1]){ cout << "NO"; return 0; }
cout << "YES";
return 0;
}import sys
def tarjan(n, adj): # Tarjan không đệ quy, như phần 3
num = [0] * (n + 1); low = [0] * (n + 1); comp = [0] * (n + 1)
on = [False] * (n + 1); it = [0] * (n + 1)
stk = []; timer = cnt = 0
for s in range(1, n + 1):
if num[s]:
continue
timer += 1; num[s] = low[s] = timer; stk.append(s); on[s] = True
call = [s]
while call:
u = call[-1]
if it[u] < len(adj[u]):
v = adj[u][it[u]]; it[u] += 1
if not num[v]:
timer += 1; num[v] = low[v] = timer
stk.append(v); on[v] = True; call.append(v)
elif on[v] and num[v] < low[u]:
low[u] = num[v]
else:
call.pop()
if call and low[u] < low[call[-1]]:
low[call[-1]] = low[u]
if low[u] == num[u]:
cnt += 1
while True:
v = stk.pop(); on[v] = False; comp[v] = cnt
if v == u:
break
return cnt, comp
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
N = 2 * n + 1 # đỉnh 2x: "x đúng", 2x + 1: "x sai"
node = lambda x: 2 * x if x > 0 else 2 * (-x) + 1
adj = [[] for _ in range(N + 1)]
for i in range(m):
a, b = int(data[2 + 2 * i]), int(data[3 + 2 * i])
adj[node(-a)].append(node(b)) # không a thì phải b
adj[node(-b)].append(node(a)) # không b thì phải a
cnt, comp = tarjan(N, adj) # đỉnh 1 không dùng, không sao
ok = all(comp[2 * x] != comp[2 * x + 1] for x in range(1, n + 1))
print("YES" if ok else "NO")
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