#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<int> u(m), v(m);
for (int i = 0; i < m; i++) {
cin >> u[i] >> v[i];
--u[i]; --v[i];
}
int ans = 0;
bool bip = true;
vector<int> f(n);
vector<int> sz(n, 1);
vector<int> c(n);
iota(f.begin(), f.end(), 0);
function<int(int)> Get = [&](int x) {
return f[x] == x ? x : Get(f[x]);
};
auto Unite = [&](int x, int y) {
int px = Get(x);
int py = Get(y);
};
vector<vector<int>> qs(4 * m);
function<void(int, int, int, int, int, int)> AddEdge = [&](int x, int l, int r, int ql, int qr, int i) {
if (ql <= l && r <= qr) {
qs[x].push_back(i);
return;
}
int mid = (l + r) / 2;
if (qr <= mid) {
AddEdge(x << 1, l, mid, ql, qr, i);
} else if (ql > mid) {
AddEdge(x << 1 | 1, mid + 1, r, ql, qr, i);
} else {
AddEdge(x << 1, l, mid, ql, qr, i);
AddEdge(x << 1 | 1, mid + 1, r, ql, qr, i);
}
};
function<void(int, int, int)> Solve = [&](int x, int l, int r) {
for (int i : qs[x]) {
Unite(u[i], v[i]);
}
if (l == r) {
ans += bip;
for (int i : qs[x]) {
Rollback();
}
return;
}
int mid = (l + r) / 2;
Solve(x << 1, l, mid);
Solve(x << 1 | 1, mid + 1, r);
for (int i : qs[x]) {
Rollback();
}
};
for (int i = 0; i < m; i++) {
if (i > 0) {
AddEdge(1, 0, m - 1, 0, i - 1, i);
}
if (i + 1 < m) {
AddEdge(1, 0, m - 1, i + 1, m - 1, i);
}
}
Solve(1, 0, m - 1);
return 0;
}
Compilation message
robots.cpp: In lambda function:
robots.cpp:25:9: warning: unused variable 'px' [-Wunused-variable]
25 | int px = Get(x);
| ^~
robots.cpp:26:9: warning: unused variable 'py' [-Wunused-variable]
26 | int py = Get(y);
| ^~
robots.cpp: In lambda function:
robots.cpp:51:9: error: 'Rollback' was not declared in this scope
51 | Rollback();
| ^~~~~~~~
robots.cpp:50:16: warning: unused variable 'i' [-Wunused-variable]
50 | for (int i : qs[x]) {
| ^
robots.cpp:59:7: error: 'Rollback' was not declared in this scope
59 | Rollback();
| ^~~~~~~~
robots.cpp:58:14: warning: unused variable 'i' [-Wunused-variable]
58 | for (int i : qs[x]) {
| ^
