#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i , j , k) for(int i = j; i < (int)k; i++)
#define pb push_back
typedef vector<int> vi;
const int N = 510;
struct dsu {
int par[N];
dsu() {
iota(par , par + N, 0);
}
int getPar(int v) {
return v == par[v] ? v : par[v] = getPar(par[v]);
}
inline bool merge(int a, int b) {
if ((a = getPar(a)) == (b = getPar(b))) return false;
par[a] = b;
return true;
}
};
dsu dd;
bitset<N> mark;
vi adj[N];
int dfs(int v) {
mark[v] =true;
int res = -1;
for (auto e : adj[v])
if (!mark[e]) {
res = dfs(e);
break;
}
if (res == -1) return v;
return res;
}
vi find_roads(int n, vi u, vi v) {
int m = u.size();
vi local;
while (local.size() < n - 1) {
mark.reset();
rep(i , 0 , n) adj[i].clear();
rep(i , 0 , m) {
adj[dd.getPar(u[i])].pb(dd.getPar(v[i]));
adj[dd.getPar(v[i])].pb(dd.getPar(u[i]));
}
int me = dfs(getPar(0));
dsu ds;
vi ask = local;
for (auto e : ask) ds.merge(u[e] , v[e]);
rep(i , 0 , m)
if (ds.getPar(u[i]) != me && ds.getPar(v[i]) != me && ds.merge(u[i] , v[i]))
ask.pb(i);
vi A, B;
rep(i , 0 , m) {
int a = ds.getPar(u[i]);
int b = ds.getPar(v[i]);
if ((a == me && b != me) || (b == me && a != me)) {
A.pb(i);
ask.pb(i);
B.pb(count_common_roads(ask));
ask.pop_back();
}
}
while (B.empty());
int res = *max_element(B.begin(), B.end());
rep(i , 0 , A.size())
if (B[i] == res) {
local.pb(A[i]);
dd.merge(u[A[i]] , v[A[i]]);
}
}
return local;
}
Compilation message
simurgh.cpp: In function 'vi find_roads(int, vi, vi)':
simurgh.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (local.size() < n - 1) {
~~~~~~~~~~~~~^~~~~~~
simurgh.cpp:59:16: error: 'getPar' was not declared in this scope
int me = dfs(getPar(0));
^~~~~~
simurgh.cpp:59:16: note: suggested alternative: 'getchar'
int me = dfs(getPar(0));
^~~~~~
getchar
