#include <iostream> #include <vector> #include <algorithm> #include <unordered_set> using namespace std; typedef long long ll; #define pb push_back #define all(a) a.begin(), a.end() #define sz(a) int(a.size()) using pii = pair<int, int>; using vi = vector<int>; using vvi = vector<vi>; // External function provided by the problem int query(vector<int> islands); vvi g; vi ak; int mid; int ile_poszlo; vi pyt; void dfs_pyt(int v, int p) { if (ile_poszlo >= mid) return; if (ak[v]) { ile_poszlo++; } pyt.pb(v); for (int u : g[v]) { if (u == p) continue; dfs_pyt(u, v); } } int findEgg(int n, vector<pii> kr) { g.assign(n + 1, vi()); for (auto [u, v] : kr) { g[u].pb(v); g[v].pb(u); } ak.assign(n + 1, 1); // 1 if potential suspect unordered_set<int> zb; for (int i = 1; i <= n; ++i) zb.insert(i); while (sz(zb) > 1) { mid = sz(zb) / 2; pyt.clear(); ile_poszlo = 0; // Start from an arbitrary suspect dfs_pyt(*zb.begin(), 0); int val = query(pyt); if (val) { // Collect old suspects in pyt BEFORE resetting ak unordered_set<int> lol; for (int ele : pyt) { if (ak[ele]) { lol.insert(ele); } } // Reset ak for (int i = 1; i <= n; ++i) ak[i] = 0; // Set new ak and zb for (int ele : lol) ak[ele] = 1; zb = move(lol); } else { for (int ele : pyt) { if (ak[ele]) { zb.erase(ele); ak[ele] = 0; } } } // Removed the unnecessary loop here } return *zb.begin(); }