#include<bits/stdc++.h>
using namespace std;
const int N = 2e5;
typedef long long ll;
ll ans = 0;
int n,m;
struct DSU{
int p,sz;
set <int> boys;
vector <int> comp;
}dsu[N];
set <int> edges[N];
multiset <int> compedges[N];
int leader(int x){
if(x == dsu[x].p)return x;
return dsu[x].p = leader(dsu[x].p);
}
bool checkedge(int x,int y){
int compx = leader(x);
int compy = leader(y);
if(compx == compy)return 1;
if(dsu[compy].boys.find(x) != dsu[compy].boys.end())return 1;
return 0;
}
bool check(int x,int y){
if(x == y)return 1;
if(compedges[x].find(y) != compedges[x].end())return 1;
return 0;
}
void connect(int x,int y){
x = leader(x);
y = leader(y);
if(x == y)return;
if(dsu[x].sz + dsu[x].boys.size() + compedges[x].size() > dsu[y].sz + dsu[y].boys.size() + compedges[y].size())swap(x,y);
///y connected to x
auto it = dsu[x].boys.begin();
while(it != dsu[x].boys.end()){
if(leader(*it) == y){
ans-=dsu[x].sz;
it = dsu[x].boys.erase(it);
edges[*it].erase(x);
compedges[y].erase(compedges[y].find(x));
}else{
it++;
}
}
///x connected to y
for(auto i:dsu[x].comp){
auto it = dsu[y].boys.find(i);
if(it != dsu[y].boys.end()){
ans-=dsu[y].sz;
dsu[y].boys.erase(it);
edges[*it].erase(y);
compedges[x].erase(compedges[x].find(y));
}
dsu[y].comp.push_back(i);
}
ans+=1ll*dsu[x].boys.size()*dsu[y].sz;
ans+=1ll*dsu[y].boys.size()*dsu[x].sz;
///x and y connected to random node
for(auto i:dsu[x].boys){
assert(leader(i) != y);
if(dsu[y].boys.find(i) != dsu[y].boys.end()){
ans-=dsu[x].sz;
ans-=dsu[y].sz;
}
dsu[y].boys.insert(i);
edges[i].erase(x);
compedges[leader(i)].erase(compedges[leader(i)].find(leader(x)));
edges[i].insert(y);
compedges[leader(i)].insert(leader(y));
}
for(auto i:compedges[x]){
compedges[y].insert(i);
}
ans+=2ll*dsu[x].sz*dsu[y].sz;
dsu[x].p = y;
dsu[y].sz+=dsu[x].sz;
///check for new connections
for(auto i:dsu[x].boys){
if(check(leader(i),x) && check(x,leader(i))){
connect(leader(i),y);
break;
}
}
dsu[x].comp.clear();
dsu[x].boys.clear();
compedges[x].clear();
}
void addedge(int x,int y){
int compx = leader(x);
int compy = leader(y);
if(checkedge(x,y))return;
if(check(compy,compx)){
connect(x,y);
}else{
dsu[compy].boys.insert(x);
edges[x].insert(compy);
compedges[compx].insert(compy);
ans+=dsu[compy].sz;
}
}
void dbg(){
for(int i = 0;i < n;i++){
cout<<"dsuinvestigate:"<<i<<'\n';
cout<<dsu[i].p<<' '<<dsu[i].sz<<'\n';
for(auto j:dsu[i].boys)cout<<j<<' ';cout<<'\n';
for(auto j:dsu[i].comp)cout<<j<<' ';cout<<'\n';
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i = 0;i < n;i++){
dsu[i] = {i,1};
dsu[i].comp.push_back(i);
}
for(int i = 0;i < m;i++){
int u,w;
cin>>u>>w;
u--;w--;
addedge(u,w);
//dbg();
cout<<ans<<'\n';
}
return 0;
}
/**
5 20
4 2
1 5
2 3
2 5
3 2
3 1
4 5
1 2
5 2
1 4
4 1
3 4
5 1
2 4
2 1
4 3
1 3
5 4
3 5
5 3
**/
Compilation message
joitter2.cpp: In function 'void dbg()':
joitter2.cpp:107:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
107 | for(auto j:dsu[i].boys)cout<<j<<' ';cout<<'\n';
| ^~~
joitter2.cpp:107:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
107 | for(auto j:dsu[i].boys)cout<<j<<' ';cout<<'\n';
| ^~~~
joitter2.cpp:108:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
108 | for(auto j:dsu[i].comp)cout<<j<<' ';cout<<'\n';
| ^~~
joitter2.cpp:108:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
108 | for(auto j:dsu[i].comp)cout<<j<<' ';cout<<'\n';
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
34652 KB |
Output is correct |
| 2 |
Correct |
13 ms |
34648 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
34652 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
34652 KB |
Output is correct |
| 2 |
Correct |
13 ms |
34648 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
34652 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
34652 KB |
Output is correct |
| 2 |
Correct |
13 ms |
34648 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
34652 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
