#include <bits/stdc++.h> #include "sphinx.h" using namespace std; #define ll long long const ll mmod = 998244353; #define vl vector<long long> #define vll vector<vector<long long>> #define pl pair<long long, long long> #define vb vector<bool> vector<int> a; vector<int> colors; vector<int> fakecolors; vector<vector<int>> graf; int n; //ll perform_experiment(vector<int> a) {return 0;} void dfs(ll v, vb& visited){ visited[v] = true; for (auto x : graf[v]){ if (visited[x] == false && fakecolors[v] == fakecolors[x]){ dfs(x, visited); } } return; } ll components(){ vb visited(n, false); ll c = 0; for (ll i = 0; i < n; i++){ c++; dfs(i, visited); } return c; } std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y){ n = N; graf.resize(n); colors.resize(n, n); fakecolors.resize(n,n); for (int i = 0; i < n; i++){ a.push_back(n); } for (int i = 0; i < X.size(); i++){ graf[X[i]].push_back(Y[i]); graf[Y[i]].push_back(X[i]); } for (ll i = 0; i < n; i++){ fakecolors[i] = n-1; a[i] = n-1; for (ll j = 0; j < i; j++){ a[j] = -1; } for (ll j = i+1; j < n; j++){ a[j] = n; } ll estimate = components(); ll real = perform_experiment(a); if (estimate == real){ colors[i] = i; continue; } ll last = -1; set<ll> found; for (ll d = 0; d < estimate-real; d++){ ll l = last+1; ll r = i; ll mid = 0; while (l <= r){ mid = (l+r)/2; //Recolor all in mid-r to N, if estimate == real, then wrong half // get component color, start binary search again from that component to r, get another... // recolor all these components to first of those. for (ll j = 0; i < n; i++){ if (l <= j && j <= mid){ fakecolors[j] = colors[j]; } else{ fakecolors[j] = n; } } fakecolors[i] = n-1; ll nest = components(); ll nrea = perform_experiment(a); if (nest == nrea){ l = mid+1; } else{ r = mid; } } last = l; found.insert(l); } ll finalcolor = *found.begin(); colors[i] = finalcolor; for (ll j = 0; j < n; j++){ auto it = found.find(colors[j]); if (it != found.end()){ colors[j] = finalcolor; } } } return colors; }