///In the name of GOD
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MXN = 4e5 + 10;
ll n, m, ans, pnt;
ll Par[MXN], Sz[MXN];
set<ll> In[MXN], Out[MXN], To[MXN], Comp[MXN];
vector<pair<ll, ll>> Q;
ll Find(ll x){
return (x == Par[x] ? x : Par[x] = Find(Par[x]));
}
void add(ll u, ll v){
if(u == v) return;
Out[u].insert(v), In[v].insert(u);
if(In[u].find(v) != In[u].end()) Q.push_back({u, v});
}
void Union(ll x, ll y){
x = Find(x), y = Find(y);
if(x == y) return;
if(Sz[x] < Sz[y]) swap(x, y);
/*
cout << "====================\n";
cout << x << ' ' << y << '\n';
cout << ans << '\n';
cout << To[x].size() << '\n';
cout << To[y].size() << '\n';
cout << "====================\n";
*/
ans -= Sz[x] * (Sz[x] - 1);
ans -= Sz[y] * (Sz[y] - 1);
ans -= 1ll * To[x].size() * (Sz[x]);
ans -= 1ll * To[y].size() * (Sz[y]);
for(auto X : In[y]) Out[X].erase(y);
for(auto X : Out[y]) In[X].erase(y);
for(auto X : In[y]) add(X, x);
for(auto X : Out[y]) add(x, X);
for(auto X : Comp[y]){
auto itr = To[x].find(X);
if(itr == To[x].end()) continue;
To[x].erase(itr);
}
for(auto X : To[y]){
if(Find(X) != x){
To[x].insert(X);
}
}
In[y].clear(), Out[y].clear(), To[y].clear();
Sz[x] += Sz[y], Par[y] = x;
ans += 1ll * To[x].size() * (Sz[x]);
ans += Sz[x] * (Sz[x] - 1);
for(auto X : Comp[y]) Comp[x].insert(X);
Comp[y].clear();
}
int main(){
ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i ++) Par[i] = i, Sz[i] = 1, Comp[i].insert(i);
for(int i = 1; i <= m; i ++){
ll u, v; cin >> u >> v;
if(Find(u) == Find(v) || To[Find(v)].find(u) != To[Find(v)].end()){
cout << ans << '\n';
continue;
}
To[Find(v)].insert(u), ans += Sz[v];
add(Find(u), Find(v));
while(pnt < Q.size()){
ll x, y; tie(x, y) = Q[pnt];
pnt ++;
Union(x, y);
}
cout << ans << '\n';
}
return 0;
}
/*!
HE'S AN INSTIGATOR,
ENEMY ELIMINATOR,
AND WHEN HE KNOCKS YOU BETTER
YOU BETTER LET HIM IN.
*/
//! N.N
Compilation message
joitter2.cpp: In function 'int main()':
joitter2.cpp:70:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | while(pnt < Q.size()){
| ~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
75500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
75500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
75500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
