#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int n,m,answer=0;
cin>>n>>m; vector<int> pr(n+1),c[n+1]; for(int i=1;i<=n;i++){pr[i]=i;c[i].push_back(i);}
set<int> in[n+1],out[n+1];
while(m--){
int a,b; cin>>a>>b;
if(pr[a]==pr[b]){}
else if(out[b].find(pr[a])==out[b].end()){
answer-=in[pr[b]].size()*c[pr[b]].size();
in[pr[b]].insert(a);
out[a].insert(pr[b]);
answer+=in[pr[b]].size()*c[pr[b]].size();
}
else{
a=pr[a],b=pr[b];
if(c[a].size()<c[b].size()) swap(a,b);
answer-=in[a].size()*c[a].size(); answer-=in[b].size()*c[b].size();
answer+=2*c[a].size()*c[b].size();
/*cout <<"------------------\n";
cout << a << " " << b << endl ;
cout << in[a].size() << " " << in[b].size() << endl ;
cout << c[a].size() << " " << c[b].size() << endl ;
cout<<"--> ";*/
pr[b]=a;
for(int x:in[b]){
if(pr[x]!=a){
in[a].insert(x);
out[x].erase(b);
out[x].insert(a);
}
else{
out[x].erase(b);
}
}
for(int x:c[b])if(out[x].find(a)!=out[x].end()){out[x].erase(a);in[a].erase(x);}
for(int x : c[b]) c[a].push_back(x);
c[b].clear();
answer+=in[a].size()*c[a].size();
}
cout<<answer<<'\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
