#include <bits/stdc++.h>
using namespace std;
int main()
{
cin.tie(nullptr)->sync_with_stdio(0);
int n;
cin >> n;
vector<set<int>> g(n + 1);
vector<set<pair<int, int>>> rg(n + 1);
vector<int> r(n + 1), sz(n + 1);
function<int(int)> f = [&](int x) {
return x == r[x] ? x : r[x] = f(r[x]);
};
long long ans = 0;
function<void(int, int)> u = [&](int a, int b) {
if(f(a) == f(b)) {
break;
}
assert(a == f(a) && b == f(b));
if(sz[a] < sz[b]) { // b do a
swap(a, b);
}
auto remove = [&](int aa, int bb) {
set<pair<int, int>>::iterator it;
while((it = rg[bb].lower_bound({aa, 0})) != rg[bb].end() && it->first == aa) {
ans -= sz[bb];
rg[bb].erase(it);
}
};
g[a].erase(b);
g[b].erase(a);
remove(a, b);
remove(b, a);
vector<int> todo;
for(int x : g[b]) {
set<pair<int, int>>::iterator it;
while((it = rg[x].lower_bound({b, 0})) != rg[x].end() && it->first == b) {
int t = it->second;
rg[x].erase(it);
rg[x].insert({a, t});
}
g[a].insert(x);
if(g[x].count(a)) {
todo.push_back(x);
}
}
ans += (long long)sz[b] * rg[a].size();
for(pair<int, int> x : rg[b]) {
g[x.first].erase(b);
g[x.first].insert(a);
if(!rg[a].count(x)) {
ans += sz[a];
rg[a].insert(x);
}
else {
ans -= sz[b]; // overcounted in line 51
}
if(g[a].count(x.first)) {
todo.push_back(x.first);
}
}
ans -= (long long)sz[a] * (sz[a] - 1);
ans -= (long long)sz[b] * (sz[b] - 1);
r[b] = a;
sz[a] += sz[b];
ans += (long long)sz[a] * (sz[a] - 1);
for(int x : todo) {
u(a, x);
}
};
auto edge = [&](int a, int b) { // a -> b
int v = a;
a = f(a);
b = f(b);
if(a == b) {
return;
}
if(!rg[b].count({a, v})) {
ans += sz[b];
rg[b].insert({a, v});
g[a].insert(b);
}
if(g[a].count(b) && g[b].count(a)) {
u(a, b);
}
};
for(int i = 1; i <= n; i++) {
r[i] = i;
sz[i] = 1;
}
int m;
cin >> m;
for(int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
edge(a, b);
cout << ans << '\n';
}
}
Compilation message
joitter2.cpp: In lambda function:
joitter2.cpp:19:13: error: break statement not within loop or switch
19 | break;
| ^~~~~
