#include <bits/stdc++.h>
using namespace std;
#include "island.h"
#define MAGIC 175
int par[175][100005];
vector<int> ss ,ee;
int M;
int find(int a, int b) {
return par[a][b] == b ? b : par[a][b] = find(a, par[a][b]);
}
vector<pair<int, int>> v;
int findd(int a, int b) {
if (par[a][b] == b)
return b;
v.emplace_back(b, par[a][b]);
return par[a][b] = find(a, par[a][b]);
}
void Init(int k, std::vector<int> F, std::vector<int> S, std::vector<int> E){
int N = F.size();
M = S.size();
for (int i = 0; i < N; i++)
g[F[i]] = 1;
reverse(S.begin(), S.end());
reverse(E.begin(), E.end());
for (int i = 0; i < k; i++)
par[0][i] = par[1][i] = i;
for (int i = 0; i < M; i++) {
int at = i / MAGIC + 1;
S[i] = F[S[i]];
E[i] = F[E[i]];
// printf(" %d %d\n", S[i], E[i]);
int ta = find(at, S[i]);
int tb = find(at, E[i]);
if (ta != tb)
par[at][ta] = tb;
if (at != (i + 1) / MAGIC + 1 || i == M - 1)
for (int j = 0; j < k; j++)
par[at + 1][j] = find(at, j);
}
ss = S, ee =E;
}
int Separate(int A, int B){
// printf("Q %d %d\n", A, B);
int lo = 0, hi = (M - 1) / MAGIC + 2;
while (lo < hi) {
int mi = (lo + hi) / 2;
if (par[mi][A] == par[mi][B])
hi = mi;
else
lo = mi + 1;
}
lo--;
int at = lo * MAGIC;
if (lo == (M - 1) / MAGIC + 1)
return 0;
int to = min(at + MAGIC, M);
int ans = M;
for (int i = at; i < to; i++) {
int ta = findd(lo, ss[i]);
int tb = findd(lo, ee[i]);
if (ta != tb) {
v.emplace_back(ta, par[lo][ta]);
par[lo][ta] = tb;
}
if (findd(lo, A) == findd(lo, B)){
ans = i;
break;
}
}
while (!v.empty()) {
par[lo][v.back().first] = v.back().second;
v.pop_back();
}
return M - ans;
}
Compilation message
island.cpp: In function 'void Init(int, std::vector<int>, std::vector<int>, std::vector<int>)':
island.cpp:30:3: error: 'g' was not declared in this scope
g[F[i]] = 1;
^
