#include <bits/stdc++.h>
using namespace std;
// int query(vector<int> islands) {
// cout << "query({";
// bool f = 1;
// for (int u : islands) {
// if (!f) cout << ", ";
// f = 0;
// cout << u;
// }
// cout << "}): ";
// int x;
// cin >> x;
// return x;
// }
int findEgg(int n, vector<pair<int, int>> bridges) {
vector<vector<int>> g(n + 1);
for (auto [a, b] : bridges) {
g[a].push_back(b);
g[b].push_back(a);
}
set<int> opts;
for (int i = 1; i <= n; ++i) opts.insert(i);
while (opts.size() > 1) {
int bdiff = 1e9, eid = -1;
for (int i = 0; i < (int) bridges.size(); ++i) {
int a = bridges[i].first, b = bridges[i].second;
if (!opts.count(a) || !opts.count(b)) continue;
function<int(int, int)> dfs = [&](int v, int p) {
int r = 1;
for (auto u : g[v]) {
if (minmax(v, u) == minmax(a, b)) continue;
if (!opts.count(u) || u == p) continue;
r += dfs(u, v);
}
return r;
};
int ax = dfs(a, -1);
int bx = dfs(b, -1);
if (int off = abs(ax - bx); off < bdiff) {
bdiff = off;
eid = i;
}
}
int a = bridges[eid].first, b = bridges[eid].second;
function<set<int>(int, int)> dfs = [&](int v, int p) {
set ret{v};
for (auto u : g[v]) {
if (minmax(v, u) == minmax(a, b)) continue;
if (!opts.count(u) || u == p) continue;
ret.merge(dfs(u, v));
}
return ret;
};
auto o = dfs(a, -1);
if (query({o.begin(), o.end()})) {
auto z = opts;
for (auto u : z) {
if (!o.count(u)) {
opts.erase(u);
}
}
} else {
for (auto u : o) {
opts.erase(u);
}
}
}
assert(opts.size() == 1);
return *opts.begin();
}
// int main() {
// int ret = findEgg(5, {{1, 2}, {1, 3}, {2, 4}, {4, 5}});
// cout << "findEgg: " << ret << endl;
// }
Compilation message
eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:56:7: error: 'query' was not declared in this scope
56 | if (query({o.begin(), o.end()})) {
| ^~~~~
