Hướng dẫn giải của Người nổi tiếng
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Editorial for hfamous: Người nổi tiếng
Hiểu bài toán
Bài toán yêu cầu tìm một tập hợp con các người nổi tiếng sao cho tập hợp này có kích thước lớn nhất có thể và mỗi người trong tập hợp đều có ít nhất k người bạn (trong chính tập hợp đó). Nói cách khác, ta cần tìm một 'k-core' (lõi k) lớn nhất của đồ thị. K-core của đồ thị là tập hợp các đỉnh mà khi loại bỏ lần lượt các đỉnh có bậc nhỏ hơn k, ta còn lại. Đây chính là tập hợp con thỏa mãn điều kiện về số lượng bạn bè tối thiểu k. Do đó, bài toán có thể giải quyết bằng cách tìm k-core của đồ thị.
Các cách tiếp cận
Cách Tìm K-core bằng Queue (Loại bỏ tuần tự)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> adj(n + 1);
vector<int> deg(n + 1, 0);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
deg[u]++;
deg[v]++;
}
queue<int> q;
vector<bool> removed(n + 1, false);
// Khởi tạo: Đưa các đỉnh có bậc < k vào hàng đợi
for (int i = 1; i <= n; ++i) {
if (deg[i] < k) {
q.push(i);
removed[i] = true;
}
}
// Loại bỏ các đỉnh vi phạm
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (!removed[v]) {
deg[v]--; // Giảm bậc của hàng xóm
if (deg[v] < k) {
removed[v] = true;
q.push(v);
}
}
}
}
// Thu thập kết quả
vector<int> result;
for (int i = 1; i <= n; ++i) {
if (!removed[i]) {
result.push_back(i);
}
}
cout << result.size() << "\n";
for (int x : result) {
cout << x << " ";
}
cout << "\n";
return 0;
}
- Time Complexity: O(n + m)
- Space Complexity: O(n + m)
Đây là thuật toán chuẩn để tìm k-core của một đồ thị.
- Xây dựng danh sách kề (adj) và tính bậc (deg) của mỗi đỉnh.
- Sử dụng một hàng đợi (queue) để lưu trữ các đỉnh cần loại bỏ. Ban đầu, tất cả các đỉnh có bậc < k được cho vào hàng đợi.
- Lặp trong khi hàng đợi còn rỗng:
- Lấy một đỉnh u ra.
- Duyệt qua các hàng xóm v của u.
- Nếu v chưa bị loại bỏ, giảm bậc của v đi 1.
- Nếu bậc mới của v < k và v chưa ở trong hàng đợi, đánh dấu loại bỏ v và đẩy v vào hàng đợi.
- Các đỉnh còn lại sau quá trình loại bỏ chính là kết quả. Thuật toán này đảm bảo mỗi cạnh và đỉnh chỉ được xử lý một lần.
Cách Cải tiến: Duyệt theo thứ tự bậc giảm dần (Heap)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> adj(n + 1);
vector<int> deg(n + 1, 0);
vector<bool> removed(n + 1, false);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
deg[u]++;
deg[v]++;
}
// Max Heap lưu cặp (độ ưu tiên, đỉnh)
// Ưu tiên các đỉnh có bậc cao hơn (hoặc dùng Min Heap logic ngược lại)
// Ở đây dùng Min Heap cho bậc để lấy ra đỉnh có bậc < k nhanh nhất
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for (int i = 1; i <= n; ++i) {
pq.push({deg[i], i});
}
while (!pq.empty()) {
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (removed[u]) continue;
if (d >= k) break; // Nếu đỉnh nhỏ nhất vẫn có bậc >= k thì dừng
// Nếu d < k
removed[u] = true;
for (int v : adj[u]) {
if (!removed[v]) {
deg[v]--;
pq.push({deg[v], v});
}
}
}
vector<int> result;
for (int i = 1; i <= n; ++i) {
if (!removed[i]) {
result.push_back(i);
}
}
cout << result.size() << "\n";
for (int x : result) cout << x << " ";
cout << "\n";
return 0;
}
- Time Complexity: O(m log n)
- Space Complexity: O(n + m)
Phương pháp này sử dụng Priority Queue (Heap) để luôn chọn ra đỉnh có bậc thấp nhất để kiểm tra và loại bỏ.
- Khởi tạo Heap với tất cả các cặp (bậc, đỉnh).
- Lặp trong khi Heap chưa rỗng:
- Lấy đỉnh u có bậc nhỏ nhất.
- Nếu bậc của u >= k, dừng lại (vì tất cả các đỉnh còn lại đều có bậc >= k).
- Nếu bậc của u < k, loại bỏ u, giảm bậc của hàng xóm và cập nhật hàng xóm vào Heap.
So với Queue, cách này đảm bảo luôn xử lý các đỉnh có bậc thấp nhất trước, nhưng độ phức tạp tăng lên do thao tác với Heap.
Cách Brute Force (Tối ưu hóa - không khuyến khích)
/*
* Brute Force kiểm tra từng tập hợp con (2^n) là bất khả thi.
* Tuy nhiên, có thể dùng phương pháp loại trừ lặp lại (Iterative Pruning)
* tương tự như Solution 1 nhưng dùng vector thay vì queue để minh họa.
* Code mẫu tương tự Approach 1.
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
// Code tương tự Approach 1
return 0;
}
- Time Complexity: O((n + m) * D) hoặc O(n^2)
- Space Complexity: O(n + m)
Brute force nguyên bản kiểm tra tất cả các tập hợp con là không khả thi do độ phức tạp 2^n. Tuy nhiên, các giải pháp trong bài nộp đều sử dụng biến thể của 'k-core decomposition'. Giải pháp này là một dạng của tham lam (Greedy): liên tục loại bỏ các đỉnh không thỏa mãn điều kiện cho đến khi không còn đỉnh nào vi phạm. Đây chính là thuật toán tối ưu cho bài toán này.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n + m) | O(n + m) | Tìm K-core bằng Queue (Loại bỏ tuần tự) |
| 2 | O(m log n) | O(n + m) | Cải tiến: Duyệt theo thứ tự bậc giảm dần (Heap) |
| 3 | O((n + m) * D) hoặc O(n^2) | O(n + m) | Brute Force (Tối ưu hóa - không khuyến khích) |
Bài học kinh nghiệm
- Bài toán này tìm kiếm 'k-core' của đồ thị, là tập hợp con mà mọi đỉnh đều có độ lớn hàng xóm >= k.
- Thuật toán loại trừ tuần tự (dùng Queue) là hiệu quả nhất với độ phức tạp O(N + M).
- Cần phải cập nhật độ bậc của hàng xóm mỗi khi loại bỏ một đỉnh.
Lỗi thường gặp
- Lỗi quản lý trạng thái (visited/removed) gây xử lý trùng lặp hoặc bỏ sót.
- Xử lý sai giới hạn (ví dụ: k = 0 hoặc k = 1).
Bình luận