// Ignut
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// int count_common_roads(vector<int> r);
struct DSU {
vector<int> p, sz;
void Init(int n) {
p.assign(n, 0);
iota(p.begin(), p.end(), 0);
sz.assign(n, 1);
}
int Get(int v) {
return p[v] == v ? v : p[v] = Get(p[v]);
}
bool Unite(int u, int v) {
u = Get(u), v = Get(v);
if (u == v) return false;
if (sz[u] > sz[v]) swap(u, v);
sz[v] += sz[u];
p[u] = v;
return true;
}
};
mt19937 rnd(11223344);
const int N = 555;
vector<int> g[N];
vector<int> U, V;
bool ans[N * N];
vector<int> vec;
vector<int> MakeVector(vector<int> &v, int l, int r) {
vector<int> res;
DSU dsu; dsu.Init(n);
for (int i = l; i <= r; i ++) {
res.push_back(v[i]);
dsu.Unite(U[v[i]], V[v[i]]);
}
for (int ind : vec) {
if (dsu.Unite(U[ind], V[ind])) {
res.push_back(ind);
}
}
return res;
}
vector<int> find_roads(int n, vector<int> u, vector<int> v) {
U = u, V = v;
int m = u.size();
for (int i = 0; i < m; i ++) {
g[u[i]].push_back(i);
g[v[i]].push_back(i);
}
if (n == 2) return {0};
vector<int> vec(m, 0);
iota(vec.begin(), vec.end(), 0);
while (true) {
shuffle(vec.begin(), vec.end(), rnd);
vector<int> v;
DSU dsu; dsu.Init(n);
for (int i = 0; i < m; i ++) {
if (dsu.Unite(u[vec[i]], v[vec[i]])) {
v.push_back(vec[i]);
}
}
int ccr = count_common_roads(v);
if (ccr == n - 1) return v;
if (ccr == 0) {
vec = v;
break;
}
}
for (int v = 0; v < n; v ++) {
int sz = g[v].size();
int total = count_common_roads(MakeVector(g[v], 0, sz - 1));
int L = -1;
for (int j = 0; j < total; j ++) {
int lo = L + 1, hi = sz - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int ccr = count_common_roads(MakeVector(g[v], L + 1, mid));
if (ccr >= 1)
hi = mid;
else
lo = mid + 1;
}
ans[g[v][lo]] = true;
L = lo;
}
}
vector<int> res;
for (int i = 0; i < m; i ++) if (ans[i]) res.push_back(i);
return res;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> MakeVector(std::vector<int>&, int, int)':
simurgh.cpp:44:23: error: 'n' was not declared in this scope
44 | DSU dsu; dsu.Init(n);
| ^
