Bài 30: Disjoint Set Union (DSU) và cây khung nhỏ nhất trong C++ và Python: Kruskal và Prim
Lời mở đầu
Ở bài 21 em đã dùng BFS/DFS để đếm thành phần liên thông của một đồ thị cho sẵn. Nhưng nếu các cạnh được thêm dần từng cái một, và sau mỗi lần thêm ta lại phải trả lời “hai đỉnh này đã thông nhau chưa?”, thì chạy lại BFS mỗi lần sẽ quá chậm. Cấu trúc Disjoint Set Union (DSU, còn gọi là Union-Find, “hợp các tập rời nhau”) sinh ra đúng cho việc đó: chỉ vài dòng code, mà mỗi thao tác gần như tức thì.
Nửa sau của bài, DSU trở thành công cụ chính của thuật toán Kruskal tìm cây khung nhỏ nhất: nối tất cả các thành phố bằng đường với tổng chi phí ít nhất. Kruskal là một thuật toán tham lam (bài 18) kinh điển, và mình sẽ giải thích thật dễ hiểu vì sao tham lam ở đây lại cho đáp án đúng. Cuối bài là thuật toán Prim, người anh em của Dijkstra (bài 29).
parent, hai phép find và union; hai tối ưu nén đường đi và gộp theo kích thước đưa mỗi thao tác về gần $O(1)$; ứng dụng DSU: đếm thành phần liên thông khi thêm cạnh, phát hiện chu trình, đếm cặp cùng nhóm, xử lý xóa cạnh bằng cách đi ngược thời gian; cây khung nhỏ nhất với Kruskal và Prim, vì sao tham lam đúng (tính chất lát cắt), cây khung lớn nhất. Có khung chạy tay DSU và Kruskal, 3 mô phỏng từng bướ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 1Bài toán gộp nhóm và hỏi cùng nhóm
Lớp có $n$ học sinh đánh số $1 \ldots n$, ban đầu không ai quen ai. Có $q$ sự kiện, mỗi sự kiện thuộc một trong hai loại:
1 u v: $u$ và $v$ kết bạn. Bạn của bạn cũng là bạn, nên thực chất là gộp nhóm bạn của $u$ với nhóm bạn của $v$.2 u v: hỏi $u$ và $v$ có cùng nhóm không (inYEShoặcNO).
Với $n, q$ tới $2 \cdot 10^5$, ta cần mỗi thao tác thật nhanh. Thử hai cách quen thuộc:
Cách 1: lưu đồ thị, mỗi câu hỏi chạy BFS/DFS. Hỏi tốn $O(n + m)$, cả bài $O(q(n + q))$, cỡ $4 \cdot 10^{10}$ phép tính. Quá chậm.
Cách 2: gán nhãn nhóm. Mảng g[i] lưu “số hiệu nhóm” của $i$. Hỏi chỉ cần so sánh g[u] == g[v], tốn $O(1)$. Nhưng gộp thì phải duyệt cả mảng, đổi mọi nhãn g[v] thành g[u]: tốn $O(n)$ mỗi lần.
| Sự kiện | g[1] | g[2] | g[3] | g[4] | g[5] | Việc phải làm |
|---|---|---|---|---|---|---|
| ban đầu | 1 | 2 | 3 | 4 | 5 | mỗi người một nhóm |
| 1 1 2 | 1 | 1 | 3 | 4 | 5 | duyệt 5 ô, đổi nhãn 2 → 1 |
| 1 3 4 | 1 | 1 | 3 | 3 | 5 | duyệt 5 ô, đổi nhãn 4 → 3 |
| 1 2 4 | 1 | 1 | 1 | 1 | 5 | duyệt 5 ô, đổi nhãn 3 → 1 |
| 2 1 4 | 1 | 1 | 1 | 1 | 5 | g[1] = g[4] → YES, chỉ 1 phép so sánh |
Bảng 1. Cách gán nhãn: hỏi rất nhanh, nhưng mỗi lần gộp phải quét lại cả mảng.
Xem code C++ / Python: cách gán nhãn ngây thơ (gộp $O(n)$) (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int g[200005]; // g[i] = nhãn nhóm của i
int main(){
int n, q;
cin >> n >> q;
for(int i = 1; i <= n; i++) g[i] = i;
while(q--){
int t, u, v;
cin >> t >> u >> v;
if(t == 1){
int a = g[u], b = g[v];
if(a != b)
for(int i = 1; i <= n; i++) // O(n) cho MỖI lần gộp
if(g[i] == b) g[i] = a;
}
else cout << (g[u] == g[v] ? "YES" : "NO") << "\n"; // O(1)
}
return 0;
}import sys
data = sys.stdin.read().split()
n, q = int(data[0]), int(data[1])
g = list(range(n + 1)) # g[i] = nhãn nhóm của i
out = []
for k in range(q):
t, u, v = int(data[2 + 3 * k]), int(data[3 + 3 * k]), int(data[4 + 3 * k])
if t == 1:
a, b = g[u], g[v]
if a != b:
for i in range(1, n + 1): # O(n) cho MỖI lần gộp
if g[i] == b:
g[i] = a
else:
out.append("YES" if g[u] == g[v] else "NO")
print("\n".join(out))Nếu đề cho $2 \cdot 10^5$ lần gộp xen kẽ câu hỏi, cách 2 tốn tới $n \cdot q = 4 \cdot 10^{10}$ phép tính. Ta muốn cả hai thao tác đều nhanh. Chìa khoá: không cần mọi phần tử biết ngay “nhóm của mình tên gì”, chỉ cần mỗi phần tử biết đi hỏi ai. Đó là ý tưởng của DSU.
Phần 2Cấu trúc DSU: parent, find, union
DSU biểu diễn mỗi nhóm bằng một cây. Mỗi đỉnh chỉ nhớ cha của nó trong mảng parent; đỉnh có parent[x] == x là gốc, và gốc chính là “người đại diện” của cả nhóm. Hai đỉnh cùng nhóm khi và chỉ khi chúng có cùng gốc.
Hình 1. Tám đỉnh chia thành ba nhóm {1, 2, 3, 4}, {5, 6}, {7, 8}. Mũi tên đi từ con lên cha. Cả hình chỉ được lưu bằng đúng một mảng parent.
Chỉ cần hai thao tác:
- find(x): đi theo
parenttừ $x$ lên tới khi gặp gốc, trả về gốc đó. Ở Hình 1:find(4)đi 4 → 3 → 1, trả về 1. - union(a, b): tìm gốc
ra = find(a),rb = find(b). Nếu khác nhau thì cho một gốc làm con của gốc kia:parent[rb] = ra. Chỉ đổi một ô của mảng!
Hỏi cùng nhóm: find(u) == find(v). Vậy là gộp không còn phải quét cả mảng. Nhưng còn một vấn đề: nếu gộp “bừa”, cây có thể biến thành một đường thẳng dài (gộp lần lượt 1–2, 2–3, 3–4, … và luôn treo gốc cũ dưới đỉnh mới), khi đó find phải đi qua $n$ đỉnh và ta lại về $O(n)$. Hai tối ưu sau đây giải quyết triệt để.
Tối ưu 1: nén đường đi (path compression). Trong lúc find(x) đi lên gốc, ta đi qua một loạt đỉnh. Tất cả chúng đều cùng gốc, vậy tiện tay nối thẳng chúng vào gốc luôn. Lần sau hỏi lại, chỉ mất một bước. Viết bằng đệ quy chỉ một dòng: return parent[x] = find(parent[x]);
Hình 2. Nén đường đi: gọi find(5) trên chuỗi 5 → 4 → 3 → 2 → 1 tốn 4 bước, nhưng sau đó 5, 4, 3 đều trỏ thẳng vào gốc 1 (mũi tên xanh).
Tối ưu 2: gộp theo kích thước (union by size). Lưu sz[r] = số đỉnh của cây gốc $r$. Khi gộp, luôn treo cây nhỏ hơn vào dưới gốc cây lớn hơn. Một đỉnh chỉ bị “tụt sâu thêm một tầng” khi cây của nó bị treo vào cây lớn hơn, tức là kích thước nhóm chứa nó ít nhất gấp đôi. Kích thước không vượt quá $n$, nên mỗi đỉnh tụt sâu tối đa $\log_2 n$ lần: cây cao không quá $\log_2 n$ ngay cả khi không nén.
Dùng cả hai tối ưu, chi phí trung bình mỗi thao tác là $O(\alpha(n))$, với $\alpha$ là hàm Ackermann ngược. Hàm này tăng chậm đến mức $\alpha(n) \le 4$ với mọi $n$ em có thể gặp (kể cả $n$ bằng số nguyên tử trong vũ trụ). Trong thực tế em cứ coi như $O(1)$.
int par[N], sz[N];
void init(int n){ for(int i = 1; i <= n; i++){ par[i] = i; sz[i] = 1; } }
int find(int x){ return par[x] == x ? x : par[x] = find(par[x]); }
bool unite(int a, int b){
a = find(a); b = find(b);
if(a == b) return false; // đã cùng nhóm
if(sz[a] < sz[b]) swap(a, b);
par[b] = a; sz[a] += sz[b];
return true; // vừa gộp hai nhóm khác nhau
}unite trả về bool rất tiện: biết ngay lần gộp có thật sự nối hai nhóm khác nhau không (dùng để đếm nhóm, phát hiện chu trình, Kruskal).Em xem DSU làm việc trong mô phỏng dưới đây. Thử chạy chế độ ngây thơ với các phép gộp 1 2, 2 3, 3 4, 4 5, 5 6 để thấy cây biến thành đường thẳng, rồi chuyển sang có tối ưu để so sánh:
Xem code C++ / Python: DSU với nén đường đi và gộp theo kích thước (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int par[200005], sz[200005];
int find(int x){ // tìm gốc của x, kèm nén đường đi
if(par[x] == x) return x;
return par[x] = find(par[x]);
}
bool unite(int a, int b){ // gộp nhóm của a và b
a = find(a); b = find(b);
if(a == b) return false; // đã cùng nhóm
if(sz[a] < sz[b]) swap(a, b); // a là nhóm lớn hơn
par[b] = a; // treo cây nhỏ vào cây lớn
sz[a] += sz[b];
return true;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, q;
cin >> n >> q;
for(int i = 1; i <= n; i++){ par[i] = i; sz[i] = 1; }
while(q--){
int t, u, v;
cin >> t >> u >> v;
if(t == 1) unite(u, v);
else cout << (find(u) == find(v) ? "YES" : "NO") << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
par = list(range(n + 1))
sz = [1] * (n + 1)
def find(x): # không đệ quy: tránh tràn ngăn xếp
root = x
while par[root] != root:
root = par[root]
while par[x] != root: # nén đường đi
par[x], x = root, par[x]
return root
def unite(a, b):
a, b = find(a), find(b)
if a == b:
return False
if sz[a] < sz[b]:
a, b = b, a
par[b] = a # treo cây nhỏ vào cây lớn
sz[a] += sz[b]
return True
out = []
for i in range(q):
t, u, v = int(data[2 + 3 * i]), int(data[3 + 3 * i]), int(data[4 + 3 * i])
if t == 1:
unite(u, v)
else:
out.append("YES" if find(u) == find(v) else "NO")
print("\n".join(out))
main()Khung chạy tay dưới đây đếm số nhóm sau $m$ phép gộp. Em để ý dòng return par[x] = find(par[x]);: lúc đi xuống thì gọi đệ quy, lúc quay về thì nén. Dữ liệu mẫu có phép gộp cuối 4 6 làm find(4) phải đi qua 2 bước rồi được nén:
find đầu tiên, và find đệ quy có thể tràn ngăn xếp khi $n = 10^6$. Dùng đủ cả hai tối ưu thì độ sâu không quá $\log_2 n \approx 20$, an toàn. Trong Python, giới hạn đệ quy mặc định chỉ 1000 và gọi hàm chậm, nên hãy viết find bằng vòng lặp như code ở trên.Một lỗi rất hay gặp khác: viết
par[a] = b với $a, b$ là đỉnh chứ không phải gốc. Luôn gọi find trước khi nối.Phần 3Ứng dụng của DSU
Coi mỗi đỉnh của đồ thị là một phần tử, mỗi cạnh là một lần unite. Khi đó nhóm của DSU chính là thành phần liên thông. Từ đây ta làm được rất nhiều việc chỉ với vài dòng:
- Đếm thành phần liên thông khi thêm cạnh: bắt đầu
comp = n; mỗi lầnunitetrả vềtruethìcomp--. Không cần chạy lại BFS. - Phát hiện chu trình: thêm cạnh $(u, v)$ mà
find(u) == find(v)nghĩa là giữa $u$ và $v$ đã có đường đi, thêm cạnh này sẽ khép thành chu trình. Một đồ thị $n$ đỉnh là cây khi và chỉ khi có đúng $n - 1$ cạnh và không cạnh nào tạo chu trình. - Đếm số cặp cùng nhóm: khi gộp nhóm $A$ (kích thước $s_A$) với nhóm $B$ (kích thước $s_B$), số cặp mới cùng nhóm tăng đúng $s_A \cdot s_B$ (mỗi người bên này ghép với mỗi người bên kia). Nhờ có sẵn mảng
sz, việc này tốn $O(1)$.
| Cạnh thêm | find hai đầu | Kết quả | Số thành phần | Số cặp cùng nhóm |
|---|---|---|---|---|
| 1 – 2 | 1, 2 | gộp, $1 \cdot 1 = 1$ cặp mới | 4 | 1 |
| 3 – 4 | 3, 4 | gộp, $1 \cdot 1 = 1$ cặp mới | 3 | 2 |
| 2 – 1 | 1, 1 | cùng gốc: tạo chu trình | 3 | 2 |
| 1 – 3 | 1, 3 | gộp, $2 \cdot 2 = 4$ cặp mới | 2 | 6 |
| 5 – 4 | 5, 1 | gộp, $1 \cdot 4 = 4$ cặp mới | 1 | 10 |
Bảng 2. Thêm lần lượt 5 cạnh vào đồ thị 5 đỉnh. Cuối cùng cả 5 đỉnh thông nhau, có $\frac{5 \cdot 4}{2} = 10$ cặp cùng nhóm, và có 1 cạnh thừa tạo chu trình.
Xem code C++ / Python: đếm thành phần, số cặp cùng nhóm và số cạnh tạo chu trình (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int par[200005];
long long sz[200005];
int find(int x){ return par[x] == x ? x : par[x] = find(par[x]); }
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++){ par[i] = i; sz[i] = 1; }
int comp = n, cycles = 0;
long long pairs = 0; // số cặp (x, y) cùng nhóm
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
int a = find(u), b = find(v);
if(a == b) cycles++; // cạnh nối hai đỉnh đã thông: tạo chu trình
else {
if(sz[a] < sz[b]) swap(a, b);
pairs += sz[a] * sz[b]; // mỗi đỉnh nhóm a ghép với mỗi đỉnh nhóm b
par[b] = a; sz[a] += sz[b];
comp--;
}
cout << comp << " " << pairs << "\n";
}
cout << cycles << "\n";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
par = list(range(n + 1))
sz = [1] * (n + 1)
def find(x):
root = x
while par[root] != root:
root = par[root]
while par[x] != root:
par[x], x = root, par[x]
return root
comp, pairs, cycles, out = n, 0, 0, []
for i in range(m):
a, b = find(int(data[2 + 2 * i])), find(int(data[3 + 2 * i]))
if a == b:
cycles += 1 # tạo chu trình
else:
if sz[a] < sz[b]:
a, b = b, a
pairs += sz[a] * sz[b]
par[b] = a
sz[a] += sz[b]
comp -= 1
out.append(f"{comp} {pairs}")
out.append(str(cycles))
print("\n".join(out))
main()Còn xóa cạnh thì sao? DSU chỉ biết gộp, không biết tách: một khi đã nối hai cây, ta không gỡ ra được. Nhưng nếu đề cho biết trước toàn bộ các lần xóa (bài toán offline), có một mẹo rất đẹp: đi ngược thời gian.
- Bắt đầu từ trạng thái cuối cùng: đồ thị chỉ còn các cạnh không bao giờ bị xóa. Dựng DSU cho các cạnh này.
- Duyệt các lần xóa từ cuối về đầu. Đi ngược thì “xóa cạnh” trở thành “thêm cạnh”, việc DSU làm rất giỏi. Trước mỗi lần thêm, ghi lại đáp án hiện tại.
- In các đáp án đã ghi theo thứ tự ngược lại.
Bài tập 8 cuối bài luyện đúng kỹ thuật này. Nhớ dấu hiệu: chỉ xóa, không thêm, biết trước hết các truy vấn → nghĩ ngay tới đảo ngược.
Phần 4Cây khung nhỏ nhất và thuật toán Kruskal
Cho đồ thị vô hướng liên thông $n$ đỉnh, mỗi cạnh có trọng số (chi phí làm đường). Một cây khung là tập con các cạnh nối tất cả $n$ đỉnh lại với nhau mà không có chu trình; nó luôn có đúng $n - 1$ cạnh. Cây khung nhỏ nhất (minimum spanning tree, MST) là cây khung có tổng trọng số nhỏ nhất. Bài toán thực tế: nối $n$ thành phố bằng mạng đường (cáp quang, ống nước…) sao cho thành phố nào cũng đi tới được thành phố khác, với chi phí ít nhất.
Hình 3. Đồ thị 6 đỉnh, 9 cạnh. Năm cạnh xanh tạo thành cây khung nhỏ nhất, tổng $2 + 3 + 3 + 5 + 6 = 19$. Các cạnh nét đứt không được dùng.
Thuật toán Kruskal là tham lam thuần tuý:
- Sắp xếp các cạnh tăng dần theo trọng số.
- Duyệt từng cạnh $(u, v)$: nếu $u$ và $v$ đang ở hai nhóm khác nhau thì nhận cạnh đó và gộp hai nhóm; nếu đã cùng nhóm thì bỏ (nhận vào sẽ tạo chu trình).
- Dừng khi đã nhận đủ $n - 1$ cạnh. Duyệt hết mà chưa đủ thì đồ thị không liên thông.
Kiểm tra “hai nhóm khác nhau” và gộp nhóm chính là find và unite của DSU. Độ phức tạp: sắp xếp $O(m \log m)$, phần DSU gần $O(m)$, tổng $O(m \log m)$.
| Thứ tự | Cạnh | w | find hai đầu | Quyết định | Tổng |
|---|---|---|---|---|---|
| 1 | 2 – 3 | 2 | khác nhóm | nhận | 2 |
| 2 | 1 – 3 | 3 | khác nhóm | nhận | 5 |
| 3 | 4 – 6 | 3 | khác nhóm | nhận | 8 |
| 4 | 1 – 2 | 4 | cùng nhóm {1, 2, 3} | bỏ: chu trình 1–2–3 | 8 |
| 5 | 3 – 4 | 5 | khác nhóm | nhận | 13 |
| 6 | 2 – 4 | 6 | cùng nhóm | bỏ: chu trình | 13 |
| 7 | 5 – 6 | 6 | khác nhóm | nhận, đủ 5 cạnh | 19 |
Bảng 3. Kruskal trên đồ thị Hình 3. Sau cạnh thứ 7 đã đủ $n - 1 = 5$ cạnh, hai cạnh 4 – 5 (7) và 3 – 5 (8) không cần xét.
Em bấm Tự chạy để xem Kruskal tô màu dần. Mỗi màu đỉnh là một nhóm của DSU, hai nhóm hợp lại thì cùng màu:
Xem code C++ / Python: thuật toán Kruskal (in tổng và các cạnh được chọn) (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int par[200005], sz[200005];
int find(int x){ return par[x] == x ? x : par[x] = find(par[x]); }
bool unite(int a, int b){
a = find(a); b = find(b);
if(a == b) return false;
if(sz[a] < sz[b]) swap(a, b);
par[b] = a; sz[a] += sz[b];
return true;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<array<int, 3>> e(m); // (w, u, v)
for(auto &x : e) cin >> x[1] >> x[2] >> x[0];
sort(e.begin(), e.end()); // tăng dần theo trọng số
for(int i = 1; i <= n; i++){ par[i] = i; sz[i] = 1; }
long long total = 0;
vector<array<int, 3>> chosen;
for(auto &x : e)
if(unite(x[1], x[2])){ // hai đầu khác nhóm: nhận cạnh
total += x[0];
chosen.push_back(x);
}
if((int)chosen.size() != n - 1){ cout << -1; return 0; } // không liên thông
cout << total << "\n";
for(auto &x : chosen) cout << x[1] << " " << x[2] << " " << x[0] << "\n";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
e = []
for i in range(m):
u, v, w = int(data[2 + 3 * i]), int(data[3 + 3 * i]), int(data[4 + 3 * i])
e.append((w, u, v))
e.sort() # tăng dần theo trọng số
par = list(range(n + 1))
sz = [1] * (n + 1)
def find(x):
root = x
while par[root] != root:
root = par[root]
while par[x] != root:
par[x], x = root, par[x]
return root
total, chosen = 0, []
for w, u, v in e:
a, b = find(u), find(v)
if a == b:
continue # tạo chu trình: bỏ
if sz[a] < sz[b]:
a, b = b, a
par[b] = a
sz[a] += sz[b]
total += w
chosen.append((u, v, w))
if len(chosen) != n - 1:
print(-1) # không liên thông
return
print(total)
print("\n".join(f"{u} {v} {w}" for u, v, w in chosen))
main()Vì sao tham lam lại đúng? Ở bài 18 mình đã nói: tham lam rất dễ sai, phải có lý do. Lý do của Kruskal là tính chất lát cắt:
Hình 4. Lát cắt $S = \{1, 2, 3\}$. Ba cạnh vắt ngang (nét đứt cam) có trọng số 6, 5, 8. Cạnh nhẹ nhất 3 – 4 (5) chắc chắn dùng được trong một cây khung nhỏ nhất.
Giải thích dễ hiểu: cây khung nào cũng phải có ít nhất một cạnh vắt ngang lát cắt, vì nếu không thì $S$ và phần còn lại không thông nhau. Giả sử có một cây khung tốt nhất $T$ lại không dùng cạnh nhẹ nhất $e$ = 3 – 4. Thêm $e$ vào $T$ sẽ tạo ra đúng một chu trình; chu trình này đi từ $S$ sang bên kia bằng $e$ thì phải quay về $S$ bằng một cạnh vắt ngang khác $f$ (ví dụ 2 – 4 nặng 6). Bỏ $f$ đi, ta lại có một cây khung, và tổng thay đổi $w(e) - w(f) \le 0$. Vậy cây mới không tệ hơn $T$ mà lại chứa $e$.
Áp vào Kruskal: khi Kruskal nhận cạnh $(u, v)$ nối hai nhóm khác nhau, lấy $S$ = nhóm đang chứa $u$. Mọi cạnh nhẹ hơn đã được xét rồi, và chúng hoặc nằm gọn trong một nhóm, hoặc đã được nhận (nên hai đầu cùng nhóm). Vậy không có cạnh nào nhẹ hơn vắt ngang $S$: cạnh $(u, v)$ chính là cạnh nhẹ nhất qua lát cắt, nhận nó là an toàn. Mỗi bước đều an toàn nên kết quả cuối cùng tối ưu.
long long.2. Luôn kiểm tra đã chọn đủ $n - 1$ cạnh chưa: thiếu nghĩa là đồ thị không liên thông (thường phải in −1).
3. Khi có nhiều cạnh cùng trọng số, cây khung nhỏ nhất có thể không duy nhất, nhưng tổng thì luôn duy nhất. Nếu đề bắt in cây, đọc kỹ xem có yêu cầu thứ tự nào không.
4. Trọng số âm không ảnh hưởng gì: Kruskal vẫn đúng (khác với Dijkstra).
Phần 5Thuật toán Prim và chọn cách nào
Kruskal nhìn toàn bộ cạnh rồi ghép các mảnh rời rạc lại. Prim làm kiểu khác: mọc một cây duy nhất từ một đỉnh xuất phát. Mỗi bước, trong các cạnh nối cây hiện tại với một đỉnh bên ngoài, chọn cạnh nhẹ nhất và kéo đỉnh đó vào cây. Đây chính là tính chất lát cắt với $S$ = tập đỉnh đã vào cây, nên Prim cũng đúng.
Cài đặt gần như giống hệt Dijkstra ở bài 29: hàng đợi ưu tiên chứa cặp (w, v). Khác biệt duy nhất: Dijkstra đẩy (d[u] + w, v) là tổng đường đi, còn Prim đẩy (w, v) là trọng số của riêng một cạnh. Lấy ra một đỉnh đã ở trong cây thì bỏ qua (cặp cũ), giống hệt mẹo “lazy” của Dijkstra.
Xem code C++ / Python: thuật toán Prim với hàng đợi ưu tiên (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> adj(n + 1); // (đỉnh kề, trọng số)
for(int i = 0; i < m; i++){
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
vector<bool> inTree(n + 1, false);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // (w, đỉnh)
pq.push({0, 1});
long long total = 0; int cnt = 0;
while(!pq.empty()){
auto [w, v] = pq.top(); pq.pop();
if(inTree[v]) continue; // cặp cũ, đỉnh đã vào cây
inTree[v] = true; total += w; cnt++;
for(auto [x, c] : adj[v])
if(!inTree[x]) pq.push({c, x});
}
if(cnt < n) cout << -1;
else cout << total;
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)]
for i in range(m):
u, v, w = int(data[2 + 3 * i]), int(data[3 + 3 * i]), int(data[4 + 3 * i])
adj[u].append((v, w))
adj[v].append((u, w))
in_tree = [False] * (n + 1)
pq = [(0, 1)] # (w, đỉnh)
total = cnt = 0
while pq:
w, v = heapq.heappop(pq)
if in_tree[v]:
continue # cặp cũ, đỉnh đã vào cây
in_tree[v] = True
total += w
cnt += 1
for x, c in adj[v]:
if not in_tree[x]:
heapq.heappush(pq, (c, x))
print(total if cnt == n else -1)
main()Cây khung lớn nhất. Muốn tổng trọng số lớn nhất (ví dụ chọn các tuyến đường có băng thông lớn nhất), chỉ cần sắp xếp cạnh giảm dần trong Kruskal, hoặc đổi dấu tất cả trọng số rồi tìm cây khung nhỏ nhất. Tính chất lát cắt vẫn đúng y nguyên khi đổi “nhẹ nhất” thành “nặng nhất”.
Cây khung nhỏ nhất còn có một tính chất đẹp: đường đi giữa hai đỉnh bất kỳ trên cây khung nhỏ nhất có cạnh lớn nhất nhỏ nhất có thể trong mọi đường đi của đồ thị gốc. Vì thế các bài “đi từ A tới B sao cho đoạn đường dốc nhất là thoải nhất” hay “xe tải chở nặng nhất bao nhiêu” thường giải bằng Kruskal: thêm cạnh theo thứ tự, dừng ngay khi A và B vừa cùng nhóm.
| Tiêu chí | Kruskal | Prim (hàng đợi ưu tiên) |
|---|---|---|
| Ý tưởng | ghép các mảnh, cạnh rẻ nhất toàn cục | mọc một cây, cạnh rẻ nhất ra ngoài cây |
| Cấu trúc cần | sắp xếp cạnh + DSU | danh sách kề + priority_queue |
| Độ phức tạp | $O(m \log m)$ | $O(m \log m)$ |
| Đồ thị không liên thông | tự nhiên cho ra rừng khung nhỏ nhất | chỉ phủ thành phần chứa đỉnh xuất phát |
| Code | ngắn, khó sai | giống Dijkstra |
| Đồ thị dày ($m \approx n^2$) | sắp xếp $n^2$ cạnh, chậm hơn | bản $O(n^2)$ không cần heap rất nhanh |
Bảng 4. So sánh Kruskal và Prim. Cả hai cho cùng tổng trọng số.
minEdge[v] mà không cần lưu hết $n^2$ cạnh. Đề hỏi “có sẵn một số đường miễn phí”: unite chúng trước rồi chạy Kruskal tiếp như thường (bài tập 7).- Lá Bài (LABAI) (Trung bình)
- Covid (ICTU P58) (Trung bình)
- Software (SOFTWARE) (Olympic 30/4 2023 – Tin học khối 10) (Trung bình)
- Bữa Tiệc (BUATIEC) (HSG12 Lâm Đồng 2025 – Bài 4) (Trung bình)
- Công Ty (HSG12 Hà Nội 2023 Vòng 1 – Bài 4) (Khó)
- Strange Printer II (LeetCode 1591) (Khó)
Bài tậpLuyện DSU và cây khung
Lớp có $n$ học sinh ($1 \le n \le 2 \cdot 10^5$) và $m$ cặp bạn thân ($0 \le m \le 2 \cdot 10^5$). Bạn của bạn cũng tính là cùng nhóm. In ra số nhóm và số người của nhóm đông nhất.
7 4
1 2
2 3
4 5
3 14 3📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
unite; unite trả về true thì số nhóm giảm 1. Nhóm đông nhất là max(sz[r]) trên các gốc $r$. Ví dụ có 4 nhóm {1, 2, 3}, {4, 5}, {6}, {7}, nhóm đông nhất 3 người. Cặp 3 1 không làm giảm số nhóm vì 1 và 3 đã cùng nhóm.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int par[200005], sz[200005];
int find(int x){ return par[x] == x ? x : par[x] = find(par[x]); }
bool unite(int a, int b){
a = find(a); b = find(b);
if(a == b) return false;
if(sz[a] < sz[b]) swap(a, b);
par[b] = a; sz[a] += sz[b];
return true;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++){ par[i] = i; sz[i] = 1; }
int groups = n;
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
if(unite(u, v)) groups--;
}
int best = 0;
for(int i = 1; i <= n; i++)
if(find(i) == i) best = max(best, sz[i]);
cout << groups << " " << best;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
par = list(range(n + 1))
sz = [1] * (n + 1)
def find(x):
root = x
while par[root] != root:
root = par[root]
while par[x] != root:
par[x], x = root, par[x]
return root
groups = n
for i in range(m):
a, b = find(int(data[2 + 2 * i])), find(int(data[3 + 2 * i]))
if a != b:
if sz[a] < sz[b]:
a, b = b, a
par[b] = a
sz[a] += sz[b]
groups -= 1
best = max(sz[i] for i in range(1, n + 1) if par[i] == i)
print(groups, best)
main()Có $q$ sự kiện ($q \le 2 \cdot 10^5$), mỗi sự kiện là một dòng: union a b (hai người tên $a$, $b$ vào chung một câu lạc bộ, hai câu lạc bộ cũ hợp nhất) hoặc ask a b (hỏi $a$, $b$ có cùng câu lạc bộ không, in YES/NO). Tên gồm chữ thường, dài không quá 20. Người chưa xuất hiện bao giờ thì đứng một mình một câu lạc bộ.
6
union an binh
union binh chi
ask an chi
ask an dung
union dung em
ask em dungYES
NO
YES📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
map/unordered_map (Python: dict): gặp tên mới thì cấp số tiếp theo và khởi tạo par, sz cho nó. Sau đó là DSU bình thường. Ví dụ: an, binh, chi về chung một nhóm nên câu hỏi đầu là YES; “dung” lúc đó chưa vào nhóm nào nên NO.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
vector<int> par, sz;
unordered_map<string, int> id;
int getId(const string &s){
auto it = id.find(s);
if(it != id.end()) return it->second;
int k = par.size();
id[s] = k; par.push_back(k); sz.push_back(1);
return k;
}
int find(int x){ return par[x] == x ? x : par[x] = find(par[x]); }
void unite(int a, int b){
a = find(a); b = find(b);
if(a == b) return;
if(sz[a] < sz[b]) swap(a, b);
par[b] = a; sz[a] += sz[b];
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int q;
cin >> q;
while(q--){
string t, a, b;
cin >> t >> a >> b;
int x = getId(a), y = getId(b);
if(t == "union") unite(x, y);
else cout << (find(x) == find(y) ? "YES" : "NO") << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
q = int(data[0])
ids, par, sz, out = {}, [], [], []
def get(s):
k = ids.get(s)
if k is None:
k = len(par)
ids[s] = k
par.append(k)
sz.append(1)
return k
def find(x):
root = x
while par[root] != root:
root = par[root]
while par[x] != root:
par[x], x = root, par[x]
return root
for i in range(q):
t, a, b = data[1 + 3 * i], get(data[2 + 3 * i]), get(data[3 + 3 * i])
a, b = find(a), find(b)
if t == b"union":
if a != b:
if sz[a] < sz[b]:
a, b = b, a
par[b] = a
sz[a] += sz[b]
else:
out.append("YES" if a == b else "NO")
print("\n".join(out))
main()Có $n$ trạm ($1 \le n \le 2 \cdot 10^5$), ban đầu chưa có dây nối nào. Lần lượt kéo $m$ dây ($m \le 2 \cdot 10^5$), dây thứ $i$ nối hai trạm $u_i, v_i$. Hỏi sau ít nhất bao nhiêu dây đầu tiên thì mọi trạm đều liên lạc được với nhau? In $0$ nếu $n = 1$, in $-1$ nếu kéo hết $m$ dây vẫn chưa liên thông.
4 5
1 2
3 4
1 2
2 3
1 44📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
comp, bắt đầu bằng $n$. Thêm từng dây, unite thành công thì comp--; ngay khi comp == 1 thì in chỉ số dây hiện tại. Ví dụ: sau dây 1 và 2 có nhóm {1, 2}, {3, 4}; dây 3 trùng nên không đổi; dây 4 nối 2 với 3 → liên thông, đáp án 4.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int par[200005], sz[200005];
int find(int x){ return par[x] == x ? x : par[x] = find(par[x]); }
bool unite(int a, int b){
a = find(a); b = find(b);
if(a == b) return false;
if(sz[a] < sz[b]) swap(a, b);
par[b] = a; sz[a] += sz[b];
return true;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++){ par[i] = i; sz[i] = 1; }
if(n == 1){ cout << 0; return 0; }
int comp = n;
for(int i = 1; i <= m; i++){
int u, v;
cin >> u >> v;
if(unite(u, v)) comp--;
if(comp == 1){ cout << i; return 0; }
}
cout << -1;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
if n == 1:
print(0)
return
par = list(range(n + 1))
sz = [1] * (n + 1)
def find(x):
root = x
while par[root] != root:
root = par[root]
while par[x] != root:
par[x], x = root, par[x]
return root
comp = n
for i in range(m):
a, b = find(int(data[2 + 2 * i])), find(int(data[3 + 2 * i]))
if a != b:
if sz[a] < sz[b]:
a, b = b, a
par[b] = a
sz[a] += sz[b]
comp -= 1
if comp == 1:
print(i + 1)
return
print(-1)
main()Mạng có $n$ máy ($n \le 2 \cdot 10^5$). Kỹ thuật viên lần lượt cắm $m$ dây ($m \le 2 \cdot 10^5$), dây thứ $i$ nối máy $u_i$ với $v_i$ (có thể $u_i = v_i$). Một dây gọi là thừa nếu lúc cắm, hai đầu của nó đã liên lạc được với nhau qua các dây cắm trước. Dòng 1 in số dây thừa $k$; nếu $k > 0$, dòng 2 in chỉ số các dây thừa theo thứ tự tăng dần.
5 6
1 2
2 3
3 1
4 5
5 4
1 42
3 5📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
find(u) == find(v) ngay trước khi cắm. Dây nối một máy với chính nó luôn thừa. Ví dụ: dây 3 (3–1) khép chu trình 1–2–3, dây 5 (5–4) trùng với dây 4. Để ý: số dây thừa luôn bằng $m - (n - \text{số nhóm cuối cùng})$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int par[200005], sz[200005];
int find(int x){ return par[x] == x ? x : par[x] = find(par[x]); }
bool unite(int a, int b){
a = find(a); b = find(b);
if(a == b) return false;
if(sz[a] < sz[b]) swap(a, b);
par[b] = a; sz[a] += sz[b];
return true;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++){ par[i] = i; sz[i] = 1; }
vector<int> extra;
for(int i = 1; i <= m; i++){
int u, v;
cin >> u >> v;
if(!unite(u, v)) extra.push_back(i); // hai đầu đã thông: dây thừa
}
cout << extra.size() << "\n";
for(int x : extra) cout << x << " ";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
par = list(range(n + 1))
sz = [1] * (n + 1)
def find(x):
root = x
while par[root] != root:
root = par[root]
while par[x] != root:
par[x], x = root, par[x]
return root
extra = []
for i in range(m):
a, b = find(int(data[2 + 2 * i])), find(int(data[3 + 2 * i]))
if a == b:
extra.append(i + 1) # hai đầu đã thông: dây thừa
continue
if sz[a] < sz[b]:
a, b = b, a
par[b] = a
sz[a] += sz[b]
print(len(extra))
if extra:
print(*extra)
main()Có $n$ thành phố ($1 \le n \le 10^5$) và $m$ phương án làm đường ($m \le 2 \cdot 10^5$), phương án $i$ nối $u_i, v_i$ với chi phí $w_i$ ($1 \le w_i \le 10^9$). Chọn một số phương án để mọi thành phố đều đi tới được nhau với tổng chi phí nhỏ nhất. In tổng đó, hoặc $-1$ nếu không thể.
6 9
1 2 4
1 3 3
2 3 2
2 4 6
3 4 5
3 5 8
4 5 7
4 6 3
5 6 619📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
long long; nhận được ít hơn $n - 1$ cạnh thì in $-1$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int par[100005], sz[100005];
int find(int x){ return par[x] == x ? x : par[x] = find(par[x]); }
bool unite(int a, int b){
a = find(a); b = find(b);
if(a == b) return false;
if(sz[a] < sz[b]) swap(a, b);
par[b] = a; sz[a] += sz[b];
return true;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<array<long long, 3>> e(m); // (w, u, v)
for(auto &x : e) cin >> x[1] >> x[2] >> x[0];
sort(e.begin(), e.end());
for(int i = 1; i <= n; i++){ par[i] = i; sz[i] = 1; }
long long total = 0; int cnt = 0;
for(auto &x : e)
if(unite(x[1], x[2])){ total += x[0]; cnt++; }
cout << (cnt == n - 1 ? total : -1);
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
e = sorted((int(data[4 + 3 * i]), int(data[2 + 3 * i]), int(data[3 + 3 * i])) for i in range(m))
par = list(range(n + 1))
sz = [1] * (n + 1)
def find(x):
root = x
while par[root] != root:
root = par[root]
while par[x] != root:
par[x], x = root, par[x]
return root
total = cnt = 0
for w, u, v in e:
a, b = find(u), find(v)
if a == b:
continue
if sz[a] < sz[b]:
a, b = b, a
par[b] = a
sz[a] += sz[b]
total += w
cnt += 1
print(total if cnt == n - 1 else -1)
main()Một công ty có $n$ chi nhánh ($n \le 10^5$) và $m$ đường truyền có thể thuê ($m \le 2 \cdot 10^5$), đường $i$ nối $u_i, v_i$ với băng thông $w_i$ ($1 \le w_i \le 10^9$). Công ty thuê đúng $n - 1$ đường sao cho các chi nhánh liên thông và tổng băng thông lớn nhất. Dữ liệu bảo đảm đồ thị liên thông. In tổng băng thông.
6 9
1 2 4
1 3 3
2 3 2
2 4 6
3 4 5
3 5 8
4 5 7
4 6 3
5 6 631📝 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 par[100005], sz[100005];
int find(int x){ return par[x] == x ? x : par[x] = find(par[x]); }
bool unite(int a, int b){
a = find(a); b = find(b);
if(a == b) return false;
if(sz[a] < sz[b]) swap(a, b);
par[b] = a; sz[a] += sz[b];
return true;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<array<long long, 3>> e(m);
for(auto &x : e) cin >> x[1] >> x[2] >> x[0];
sort(e.rbegin(), e.rend()); // giảm dần theo băng thông
for(int i = 1; i <= n; i++){ par[i] = i; sz[i] = 1; }
long long total = 0;
for(auto &x : e)
if(unite(x[1], x[2])) total += x[0];
cout << total;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
e = sorted(((int(data[4 + 3 * i]), int(data[2 + 3 * i]), int(data[3 + 3 * i])) for i in range(m)), reverse=True)
par = list(range(n + 1))
sz = [1] * (n + 1)
def find(x):
root = x
while par[root] != root:
root = par[root]
while par[x] != root:
par[x], x = root, par[x]
return root
total = 0
for w, u, v in e: # giảm dần theo băng thông
a, b = find(u), find(v)
if a != b:
if sz[a] < sz[b]:
a, b = b, a
par[b] = a
sz[a] += sz[b]
total += w
print(total)
main()Tỉnh có $n$ xã ($n \le 10^5$). Đã có sẵn $k$ con đường (miễn phí), đường thứ $i$ nối $a_i, b_i$. Có thêm $m$ phương án làm đường mới ($k, m \le 2 \cdot 10^5$), phương án $j$ nối $u_j, v_j$ với chi phí $w_j$ ($w_j \le 10^9$). Tìm tổng chi phí nhỏ nhất để mọi xã đều thông nhau, hoặc $-1$ nếu không thể.
Input: dòng đầu $n, k, m$; $k$ dòng tiếp là các đường có sẵn; $m$ dòng cuối là các phương án.
5 2 4
1 2
3 4
2 3 5
1 4 2
4 5 3
1 5 105📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
unite chúng hết trước, và mỗi lần thành công thì bớt một “cạnh cần thêm”. Sau đó chạy Kruskal trên các phương án như thường. Kiểm tra cuối cùng phải dựa vào số nhóm còn lại bằng 1 chứ không phải số cạnh đã mua. Ví dụ: có sẵn {1, 2} và {3, 4}; mua 1–4 (2) rồi 4–5 (3), tổng 5.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int par[100005], sz[100005];
int find(int x){ return par[x] == x ? x : par[x] = find(par[x]); }
bool unite(int a, int b){
a = find(a); b = find(b);
if(a == b) return false;
if(sz[a] < sz[b]) swap(a, b);
par[b] = a; sz[a] += sz[b];
return true;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, k, m;
cin >> n >> k >> m;
for(int i = 1; i <= n; i++){ par[i] = i; sz[i] = 1; }
int comp = n;
for(int i = 0; i < k; i++){ // đường có sẵn: nối trước, miễn phí
int a, b;
cin >> a >> b;
if(unite(a, b)) comp--;
}
vector<array<long long, 3>> e(m);
for(auto &x : e) cin >> x[1] >> x[2] >> x[0];
sort(e.begin(), e.end());
long long total = 0;
for(auto &x : e)
if(unite(x[1], x[2])){ total += x[0]; comp--; }
cout << (comp == 1 ? total : -1);
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, k, m = int(data[0]), int(data[1]), int(data[2])
par = list(range(n + 1))
sz = [1] * (n + 1)
def find(x):
root = x
while par[root] != root:
root = par[root]
while par[x] != root:
par[x], x = root, par[x]
return root
def unite(a, b):
a, b = find(a), find(b)
if a == b:
return False
if sz[a] < sz[b]:
a, b = b, a
par[b] = a
sz[a] += sz[b]
return True
comp, p = n, 3
for _ in range(k): # đường có sẵn: nối trước, miễn phí
if unite(int(data[p]), int(data[p + 1])):
comp -= 1
p += 2
e = sorted((int(data[p + 3 * j + 2]), int(data[p + 3 * j]), int(data[p + 3 * j + 1])) for j in range(m))
total = 0
for w, u, v in e:
if unite(u, v):
total += w
comp -= 1
print(total if comp == 1 else -1)
main()Mạng có $n$ máy và $m$ dây ($n, m \le 2 \cdot 10^5$), dây $i$ nối $u_i, v_i$. Lần lượt có $q$ lần cắt ($q \le m$), lần thứ $j$ cắt dây có chỉ số $c_j$; các $c_j$ đôi một khác nhau. Sau mỗi lần cắt, in số thành phần liên thông của mạng.
4 4
1 2
2 3
3 4
4 1
3
2
4
11
2
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 par[200005], sz[200005];
int find(int x){ return par[x] == x ? x : par[x] = find(par[x]); }
bool unite(int a, int b){
a = find(a); b = find(b);
if(a == b) return false;
if(sz[a] < sz[b]) swap(a, b);
par[b] = a; sz[a] += sz[b];
return true;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m, q;
cin >> n >> m;
vector<int> U(m + 1), V(m + 1);
for(int i = 1; i <= m; i++) cin >> U[i] >> V[i];
cin >> q;
vector<int> c(q + 1);
vector<bool> cut(m + 1, false);
for(int j = 1; j <= q; j++){ cin >> c[j]; cut[c[j]] = true; }
for(int i = 1; i <= n; i++){ par[i] = i; sz[i] = 1; }
int comp = n;
for(int i = 1; i <= m; i++) // trạng thái cuối: các dây không bị cắt
if(!cut[i] && unite(U[i], V[i])) comp--;
vector<int> ans(q + 1);
for(int j = q; j >= 1; j--){
ans[j] = comp; // đáp án sau lần cắt j
if(unite(U[c[j]], V[c[j]])) comp--; // đi ngược: thêm lại dây c[j]
}
for(int j = 1; j <= q; j++) cout << ans[j] << "\n";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
U = [0] + [int(data[2 + 2 * i]) for i in range(m)]
V = [0] + [int(data[3 + 2 * i]) for i in range(m)]
p = 2 + 2 * m
q = int(data[p])
c = [0] + [int(x) for x in data[p + 1:p + 1 + q]]
cut = [False] * (m + 1)
for j in range(1, q + 1):
cut[c[j]] = True
par = list(range(n + 1))
sz = [1] * (n + 1)
def find(x):
root = x
while par[root] != root:
root = par[root]
while par[x] != root:
par[x], x = root, par[x]
return root
def unite(a, b):
a, b = find(a), find(b)
if a == b:
return False
if sz[a] < sz[b]:
a, b = b, a
par[b] = a
sz[a] += sz[b]
return True
comp = n
for i in range(1, m + 1): # trạng thái cuối: các dây không bị cắt
if not cut[i] and unite(U[i], V[i]):
comp -= 1
ans = [0] * (q + 1)
for j in range(q, 0, -1):
ans[j] = comp # đáp án sau lần cắt j
if unite(U[c[j]], V[c[j]]): # đi ngược: thêm lại dây c[j]
comp -= 1
print("\n".join(map(str, ans[1:])))
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