#include <bits/stdc++.h>
using namespace std;
const int N = 500;
int par[N], edge[N], depth[N], deg[N], matches[N], dsu[N], n;
bool royal[N], visited[N], observed[N];
vector<int> span, ans, not_ans, u, v;
vector<array<int, 2>> adj[N];
void dfs(int u) {
visited[u] = true;
for (auto [c, e] : adj[u]) {
if (!visited[c]) {
span.push_back(e);
depth[c] = depth[u] + 1;
edge[c] = e;
par[c] = u;
dfs(c);
}
}
}
int find(int u) {
return dsu[u] < 0 ? u : dsu[u] = find(dsu[u]);
}
bool unite(int u, int v) {
u = find(u), v = find(v);
if (u != v) {
if (-dsu[u] > -dsu[v]) {
swap(u, v);
}
dsu[v] += dsu[u];
dsu[u] = v;
return true;
}
return false;
}
int get(vector<int> &tree) {
fill(dsu, dsu + n, -1);
for (auto i : tree) {
unite(u[i], v[i]);
}
for (auto i : not_ans) {
if (unite(u[i], v[i])) {
tree.push_back(i);
}
}
int offset = 0;
for (auto i : ans) {
if (unite(u[i], v[i])) {
tree.push_back(i);
++offset;
}
}
return offset;
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
int m = u.size(); ::n = n, ::u = u, ::v = v;
for (int i = 0; i < m; ++i) {
adj[u[i]].push_back({v[i], i});
adj[v[i]].push_back({u[i], i});
}
dfs(0);
int init = count_common_roads(span);
for (int i = 0; i < m; ++i) {
if (depth[u[i]] > depth[v[i]]) {
swap(u[i], v[i]);
}
if (depth[u[i]] + 1 == depth[v[i]]) {
continue;
}
bool learn = false;
for (int j = v[i]; j != u[i]; j = par[j]) {
learn |= !observed[j];
}
if (!learn) {
continue;
}
int reference = -1, mini = n - 1, maxi = 0;
for (int j = v[i]; j != u[i]; j = par[j]) {
vector<int> cycle = span;
cycle.erase(find(cycle.begin(), cycle.end(), edge[j]));
cycle.push_back(i);
int value = -1;
if (!observed[j]) {
value = matches[j] = count_common_roads(cycle);
} else if (reference == -1) {
value = count_common_roads(cycle);
reference = j;
}
if (value != -1) {
mini = min(mini, value);
maxi = max(maxi, value);
}
}
for (int j = v[i]; j != u[i]; j = par[j]) {
if (!observed[j]) {
observed[j] = true;
if (mini == maxi) {
if (reference == -1) {
royal[j] = mini < init;
} else {
royal[j] = royal[reference];
}
} else {
royal[j] = matches[j] == mini;
}
}
}
}
for (int i = 1; i < n; ++i) {
(royal[i] || !observed[i] ? ans : not_ans).push_back(edge[i]);
}
vector<int> stk;
for (int i = 0; i < n; ++i) {
vector<int> star;
for (auto [j, e] : adj[i]) {
if (count(ans.begin(), ans.end(), e) == 0) {
star.push_back(e);
}
}
int offset = get(star);
deg[i] = count_common_roads(star) - offset;
if (deg[i] == 1) {
stk.push_back(i);
}
}
while (!stk.empty()) {
int i = stk.back();
stk.pop_back();
if (deg[i] == 0) {
continue;
}
vector<int> candidates;
for (auto [j, e] : adj[i]) {
if (count(ans.begin(), ans.end(), e) == 0) {
candidates.push_back(e);
}
}
int low = 0, high = candidates.size() - 1;
while (low < high) {
int mid = (low + high) / 2;
vector<int> star = vector<int>(candidates.begin(), candidates.begin() + mid + 1);
int offset = get(star);
if (count_common_roads(star) - offset > 0) {
high = mid;
} else {
low = mid + 1;
}
}
int e = candidates[low], j = i ^ u[e] ^ v[e];
ans.push_back(e);
if (--deg[j] == 1) {
stk.push_back(j);
}
}
return ans;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:75:16: error: 'count_common_roads' was not declared in this scope
75 | int init = count_common_roads(span);
| ^~~~~~~~~~~~~~~~~~
