#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl "\n"
int par[100001];
int size2[100001];
set<pair<int,int>> inc[100001];
set<pair<int,int>> out[100001];
int find(int no){
if(par[no]==no){
return no;
}
par[no]=find(par[no]);
return par[no];
}
set<int> wait;
ll ans=0;
ll count(int aa){
return (ll)size2[aa]*(size2[aa]-1)+(ll)inc[aa].size()*size2[aa];
}
void merge(int aa,int bb){
ans-=(count(aa)+count(bb));
if((inc[aa].size()+out[aa].size())<(inc[bb].size()+out[bb].size())){
swap(aa,bb);
}
for(auto no:inc[bb]){
if(no.a==aa){
auto it=out[aa].find({bb,no.b});
out[aa].erase(it);
continue;
}
auto it=inc[no.a].lower_bound({aa,0});
if(it!=inc[no.a].end() and it->a==aa){
wait.insert(no.a);
}
out[no.a].insert({aa,no.b});
auto tt=out[no.a].find({bb,no.b});
out[no.a].erase(tt);
inc[aa].insert(no);
}
for(auto no:out[bb]){
if(no.a==aa){
auto it=inc[aa].find({bb,no.b});
inc[aa].erase(it);
continue;
}
auto it=out[no.a].lower_bound({aa,0});
if(it!=out[no.a].end() and it->a==aa){
wait.insert(no.a);
}
inc[no.a].insert({aa,no.b});
auto tt=inc[no.a].find({bb,no.b});
inc[no.a].erase(tt);
out[aa].insert(no);
}
inc[bb].clear();
out[bb].clear();
par[bb]=aa;
size2[aa]+=size2[bb];
ans+=count(aa);
//cout<<":: "<<ans<<" "<<aa<<" "<<bb<<" "<<inc[aa].size()<<endl;
if(wait.size()>0){
int xx=*(wait.begin());
wait.erase(wait.begin());
merge(aa,xx);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int tot=0;
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++){
par[i]=i;
size2[i]=1;
}
int aa,bb;
for(int i=0;i<m;i++){
cin>>aa>>bb;
aa-=1;
bb-=1;
int ac=aa;
aa=find(aa);
bb=find(bb);
if(aa==bb){
continue;
}
if(out[aa].find({bb,ac})==out[aa].end()){
auto it=inc[aa].lower_bound({bb,0});
if(it!=inc[aa].end() and it->a==bb){
merge(aa,bb);
}
else{
inc[bb].insert({aa,ac});
out[aa].insert({bb,ac});
ans+=size2[bb];
}
}
cout<<ans<<endl;
}
return 0;
}
Compilation message
joitter2.cpp: In function 'int main()':
joitter2.cpp:79:6: warning: unused variable 'tot' [-Wunused-variable]
int tot=0;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
9856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
9856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
9856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
