#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#include <C:\debug.hpp>
#endif // ONLINE_JUDGE
#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define Neco "Joitter"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 2e5 + 7
using namespace std;
const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
return uniform_int_distribution<ll> (l, r)(rng);
}
int n, q; ll ans;
int lab[maxn];
vector<pair<int, int>> Wait;
set<int> In[maxn], Out[maxn], C[maxn];
int get_rt(int u) { return lab[u] < 0 ? u : lab[u] = get_rt(lab[u]); }
int size(int u) { return C[u].size() + In[u].size() + Out[u].size(); }
void Add(int u, int v) {
u = get_rt(u), v = get_rt(v);
In[v].insert(u), Out[u].insert(v);
if(Out[v].count(u)) Wait.push_back({u, v});
}
void uni(int u, int v) {
u = get_rt(u), v = get_rt(v); if(u == v) return;
if(size(u) < size(v)) swap(u, v);
ans += 1ll * (-lab[u] * C[v].size()) + 1ll * (-lab[v] * C[u].size());
lab[u] += lab[v], lab[v] = u;
for(int x : C[v]) {
if(C[u].count(x)) ans -= -lab[u];
else C[u].insert(x);
}
for(int x : In[v]) {
Out[x].erase(v), Add(x, u);
}
for(int x : Out[v]) {
In[x].erase(v), Add(u, x);
}
In[v].clear(), Out[v].clear(), C[v].clear();
}
void solve()
{
cin >> n >> q;
fi(i, 1, n) lab[i] = -1, C[i] = {i};
fi(i, 1, q) {
int u, v; cin >> u >> v;
v = get_rt(v);
if(get_rt(u) != v && !C[v].count(u)) {
C[v].insert(u), ans += -lab[v];
u = get_rt(u);
Add(u, v);
while(!Wait.empty()) {
int x, y; tie(x, y) = Wait.back();
Wait.pop_back();
uni(x, y);
}
}
cout << ans << '\n';
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen(Neco".inp", "r")) {
freopen(Neco".inp", "r", stdin);
freopen(Neco".out", "w", stdout);
}
int nTest = 1;
// cin >> nTest;
while(nTest--)
{
solve();
}
return 0;
}
Compilation message
joitter2.cpp:3:10: fatal error: C:\debug.hpp: No such file or directory
3 | #include <C:\debug.hpp>
| ^~~~~~~~~~~~~~
compilation terminated.
