#include <iostream> #include <vector> #include <algorithm> #include <unordered_set> using namespace std; typedef long long ll; #define st first #define nd second #define f(a, c, b) for (int a = c; b > a; a++) #define pb push_back #define all(a) a.begin(), a.end() #define sz(a) int(a.size()) #define DUZO 1000000000000000000 using pii = pair<int, int>; using pll = pair<ll, ll>; using vi = vector<int>; using vvi = vector<vi>; int query(vector<int> islands); vvi g; vi ak; vi out; int mid; int ile_poszlo; vi pyt; /*int query(vi a) { for (int ele: a) { if (ele == 3) return 1; } return 0; }*/ 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 || out[v]) continue; dfs_pyt(u, v); } } int findEgg(int n, vector<pii> kr) { g = {}; g.resize(n + 1); for (auto [u, v]: kr) { g[u].pb(v); g[v].pb(u); } ak = {}; out = {}; out.resize(n+ 1, 0); ak.resize(n + 1, 1); //czy jest w potencjalnym solvie unordered_set<int> zb; f(i, 1, n+ 1) zb.insert(i); while (sz(zb)>1) { mid = sz(zb)/2; pyt = {}; ile_poszlo = 0; dfs_pyt(*(zb.begin()), 0); int val = query(pyt); if (val) { f(i, 1, n+ 1) ak[i] = 0; unordered_set<int> lol; for (int ele: pyt) { lol.insert(ele); ak[ele] = 1; } zb= lol; } else { for (int ele: pyt) { zb.erase(ele); ak[ele] = 0; } } f(i, 1, n+ 1) { if (ak[i]) continue; bool git = false; for (int ele: g[i]) { if (ak[ele]) { git = true; } } if (!git) out[i] = 1; } } return *(zb.begin()); } /*int main() { int n = 7; vector<pii> kr = {{1, 2}, {1, 3}, {2, 4}, {2, 5}, {4, 6}, {3, 7}}; cout << findEgg(n, kr) << "\n"; }*/