//besmellah
#include <bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
using namespace std;
using ar = array<int, 2>;
const int N = 3e5 + 5;
const long long INF = 1ll << 60;
int ans = 0;
namespace dsu {
int dpr[N], sz[N];
set<array<int, 2>> in[N], out[N];
//sz[v] => sum of in[v].second
void init() {
memset(dpr, -1, sizeof dpr);
}
int gpr(int x) {
return dpr[x] < 0 ? x : dpr[x] = gpr(dpr[x]);
}
bool ise(int v, int u) {//u <- v
auto it = in[u].lower_bound({v, -1});
return it != in[u].end() && (*it)[0] == v;
}
void merge(int u, int v) {
u = gpr(u), v = gpr(v);
if (u == v) return;
if (in[u].size() + out[u].size() > in[v].size() + out[v].size()) swap(u, v);
auto it = in[u].lower_bound({v, -1});
while (it != in[u].end() && (*it)[0] == v) {
ans -= -dpr[v];
out[v].erase({u, (*it)[1]});
in[u].erase(it);
it = in[u].lower_bound({v, -1});
}
it = in[v].lower_bound({u, -1});
while (it != in[v].end() && (*it)[0] == u) {
ans -= -dpr[u];
out[u].erase({v, (*it)[1]});
in[v].erase(it);
it = in[v].lower_bound({u, -1});
}
ans += dpr[u] * dpr[v] * 2;
vector<int> q;
int re = 0;
for (auto [rt, x]: in[u]) re += in[v].contains({rt, x});
int only_v = in[v].size() - re;
ans += -dpr[u] * only_v;
for (auto [rt, x]: in[u]) if (!in[v].contains({rt, x}))
ans += -dpr[v];
for (auto [rt, x]: in[u]) {
in[v].insert({rt, x});
out[rt].erase({u, x});
out[rt].insert({v, x});
if (ise(v, rt) && ise(rt, v)) q.push_back(rt);
}
for (auto [rt, x]: out[u]) {
out[v].insert({rt, x});
in[rt].erase({u, x});
in[rt].insert({v, x});
if (ise(v, rt) && ise(rt, v)) q.push_back(rt);
}
in[u].clear(), out[u].clear();
dpr[v] += dpr[u];
dpr[u] = v;
for (auto x: q) merge(x, v);
}
void E(int u, int v) {
int tu = u;
u = gpr(u), v = gpr(v);
if (u == v || in[v].contains({u, tu})) return;
in[v].insert({u, tu});
out[u].insert({v, tu});
ans -= dpr[v];
if (ise(u, v) && ise(v, u)) {
merge(u, v);
}
}
}
int n, m;
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
dsu::init();
cin >> n >> m;
set<ar> S;
FOR(i, 0, m) {
int u, v;
cin >> u >> v;
--u, --v;
dsu::E(u, v);
cout << ans << '\n';
}
return 0;
}
Compilation message
joitter2.cpp: In function 'void dsu::merge(long long int, long long int)':
joitter2.cpp:52:55: error: 'class std::set<std::array<long long int, 2> >' has no member named 'contains'
52 | for (auto [rt, x]: in[u]) re += in[v].contains({rt, x});
| ^~~~~~~~
joitter2.cpp:55:54: error: 'class std::set<std::array<long long int, 2> >' has no member named 'contains'
55 | for (auto [rt, x]: in[u]) if (!in[v].contains({rt, x}))
| ^~~~~~~~
joitter2.cpp: In function 'void dsu::E(long long int, long long int)':
joitter2.cpp:79:37: error: 'class std::set<std::array<long long int, 2> >' has no member named 'contains'
79 | if (u == v || in[v].contains({u, tu})) return;
| ^~~~~~~~
