#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10 , M = 3e5 + 10;
int n , m;
long long fin_ans = 0;
struct DSU{
set <int> st[N] , in[N] , out[N];
int sz[N] , par[N];
void Build()
{
for(int i = 1 ; i <= n ; i++)
{
sz[i] = 1;
st[i].insert(i);
in[i].insert(i);
out[i].inesrt(i);
}
}
int root(int v)
{
return (par[v] == 0 ? v : par[v] = root(par[v]));
}
void Merge(int a , int b)
{
fin_ans -= 1LL * sz[a] * ((long long)st[a].size() - 1);
fin_ans -= 1LL * sz[b] * ((long long)st[b].size() - 1);
if(sz[a] > sz[b])
swap(a , b);
for(auto u : st[a])
st[b].insert(u);
for(auto u : out[a])
{
out[b].insert(u);
in[u].erase(a);
in[u].insert(b);
}
for(auto u : in[a])
{
in[b].insert(u);
out[u].erase(a);
out[u].insert(b);
}
st[a].clear();
in[a].clear();
out[a].clear();
par[a] = b;
sz[b] += sz[a];
fin_ans += 1LL * sz[b] * ((long long)st[b].size() - 1);
}
void Add(int a , int b)
{
int ra = root(a) , rb = root(b);
if(st[ra].find(b) != st[ra].end())
return;
st[ra].insert(b);
out[ra].insert(rb);
in[rb].insert(ra);
fin_ans += sz[ra];
if(out[rb].find(ra) != out[rb].end())
{
Merge(ra , rb);
return;
}
}
} dsu;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
dsu.Build();
while(m--)
{
int u , v; cin >> u >> v;
dsu.Add(v , u);
cout << fin_ans << '\n';
}
return 0;
}
Compilation message
joitter2.cpp: In member function 'void DSU::Build()':
joitter2.cpp:19:11: error: 'class std::set<int>' has no member named 'inesrt'; did you mean 'insert'?
19 | out[i].inesrt(i);
| ^~~~~~
| insert
