Hướng dẫn giải của [2425 KS1] Bài 5: Chia tay
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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.
Hướng dẫn giải
Bài cho một cây N đỉnh, cần tìm khoảng cách lớn nhất giữa hai đỉnh (đường kính của cây), khoảng cách là số cạnh đi qua.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 5000~
Với mỗi đỉnh s, chạy BFS từ s để tính khoảng cách tới mọi đỉnh, lấy khoảng cách lớn nhất trong tất cả các lần BFS. Nếu chỉ nộp sub này: đúng 20/20 test (đã chấm riêng).
Sub 2: Hai lần BFS — ~O(n)~
Tính chất của cây: BFS từ một đỉnh bất kỳ tìm được đỉnh A xa nhất. Từ A, BFS lần nữa, khoảng cách xa nhất tìm được chính là đường kính. Bẫy: cây có thể suy biến thành một đường dài, nên không dùng đệ quy DFS (có thể tràn ngăn xếp), dùng BFS với hàng đợi. Nếu chỉ nộp sub này: đúng 20/20 test (đã chấm riêng).
Chương trình hoàn chỉnh
Hàm main đọc cây. Nếu N \le 5000 gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> adj;
// Sub 1: vet can O(n^2) - BFS tu moi dinh, lay khoang cach lon nhat. Dung khi n <= 5000.
void sub1() {
int best = 0;
vector<int> dist(n + 1);
for (int s = 1; s <= n; s++) {
fill(dist.begin(), dist.end(), -1);
queue<int> q;
q.push(s);
dist[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
best = max(best, dist[u]);
for (int v : adj[u])
if (dist[v] < 0) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
cout << best << "\n";
}
// BFS tra ve dinh xa nhat va khoang cach toi no.
pair<int, int> bfsFar(int s) {
vector<int> dist(n + 1, -1);
queue<int> q;
q.push(s);
dist[s] = 0;
int far = s;
while (!q.empty()) {
int u = q.front(); q.pop();
if (dist[u] > dist[far]) far = u;
for (int v : adj[u])
if (dist[v] < 0) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
return {far, dist[far]};
}
// Sub 2: day du, O(n). Cay: BFS tu 1 tim dinh A xa nhat, BFS tu A duoc duong kinh.
void sub2() {
int a = bfsFar(1).first;
cout << bfsFar(a).second << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
adj.assign(n + 1, {});
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
if (n <= 5000) sub1(); // do thi nho: vet can cho chac
else sub2();
return 0;
}
Bình luận