Hướng dẫn giải của [200 đề thầy Đức] Bài 183: Vòng tròn bạn bè
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
Mỗi học sinh chỉ có đúng một bạn kết bạn đi ra, nên các học sinh tạo thành các vòng và các đường dẫn đổ vào vòng. Hai học sinh cùng vòng khi cả hai nằm trên cùng một vòng; khoảng cách từ ~z~ đến ~t~ là số bước đi từ ~z~ tới ~t~ trừ 1.
Sub 1: Đi theo chuỗi kết bạn — ~O(n)~ mỗi câu hỏi, dùng khi ~n \le 1000~
Từ ~z~ đi theo chuỗi kết bạn. Nếu quay lại ~z~ mà đã gặp ~t~ thì có vòng chung, khoảng cách là số bước - 1; nếu không quay lại ~z~ thì không chung vòng. Nếu chỉ nộp sub này: đúng 4/4 test.
Sub 2: Gán vòng một lần — ~O(n + Q)~
Tìm các vòng một lần, gán cho mỗi học sinh số hiệu vòng và vị trí trên vòng, rồi trả lời mỗi câu hỏi trong ~O(1)~. Nếu chỉ nộp sub này: đúng 4/4 test.
Chương trình hoàn chỉnh
Nếu ~n \le 1000~ dùng sub 1, còn lại dùng sub 2. 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; // so hoc sinh
map<long long, long long> nxt; // nxt[x] = y: x ket ban voi y (moi nguoi co dung 1 ban)
vector<pair<long long, long long>> Qs; // cac cap (z, t) can kiem tra
// Sub 1: voi moi cap (z, t), di theo chuoi ket ban tu z. Neu quay lai z (z nam tren vong)
// va gap t truoc do thi Yes, khoang cach = so buoc - 1. Dung khi n <= 1000.
void sub1() {
for (auto &q : Qs) {
long long z = q.first, t = q.second;
long long cur = z, steps = 0, foundAt = -1;
bool back = false;
while (steps <= 2LL * n + 5) {
auto it = nxt.find(cur);
if (it == nxt.end()) break;
cur = it->second;
steps++;
if (cur == t && foundAt < 0) foundAt = steps;
if (cur == z) { back = true; break; }
}
if (back && foundAt > 0) cout << "Yes " << foundAt - 1 << "\n";
else cout << "No\n";
}
}
// Sub 2: tim cac vong trong do thi (moi dinh co dung 1 canh ra), gan chi so vong va vi tri tren vong,
// roi tra loi moi cau hoi O(1)
void sub2() {
map<long long, int> id;
auto gid = [&](long long x) {
auto it = id.find(x);
if (it != id.end()) return it->second;
int k = id.size();
id[x] = k;
return k;
};
for (auto &e : nxt) { gid(e.first); gid(e.second); }
for (auto &q : Qs) { gid(q.first); gid(q.second); }
int V = id.size();
vector<int> nx(V, -1);
for (auto &e : nxt) nx[gid(e.first)] = gid(e.second);
vector<int> vis(V, 0), cyc(V, -1), pos(V, 0), clen;
int stamp = 0;
for (int s = 0; s < V; s++) {
if (vis[s]) continue;
stamp++;
int v = s;
while (v != -1 && vis[v] == 0) { vis[v] = stamp; v = nx[v]; }
if (v != -1 && vis[v] == stamp) { // gap dinh cua duong dang di: day la mot vong moi
int cid = clen.size(), u = v, k = 0;
do { cyc[u] = cid; pos[u] = k++; u = nx[u]; } while (u != v);
clen.push_back(k);
}
}
for (auto &q : Qs) {
int A = id[q.first], B = id[q.second];
if (cyc[A] < 0 || cyc[B] < 0 || cyc[A] != cyc[B]) { cout << "No\n"; continue; }
int L = clen[cyc[A]];
int steps = (A == B) ? L : ((pos[B] - pos[A] + L) % L);
cout << "Yes " << steps - 1 << "\n";
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) {
long long x, y;
cin >> x >> y;
nxt[x] = y;
}
long long z, t;
while (cin >> z >> t) {
if (z == 0 && t == 0) break;
Qs.push_back({z, t});
}
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận