#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n,m;
int p[10005];
int s[100005];
int par(int i){
if (p[i]==i) return i;
else return p[i]=par(p[i]);
}
set<ii> al[100005]; //point out
set<int> al2[100005]; //point in
int num[100005]; //number of edges pointing into
int IDX=0;
set<int> id[300005]; //id of those guys in the equiv class who are pointing
vector<ii> proc;
int get(int A,int B){
auto it=al[A].lb(ii(B,-1));
if (it==al[A].end() || (*it).fi!=B) return -1;
else return (*it).se;
}
signed main(){
cin.tie(0);
cout.tie(0);
cin.sync_with_stdio(false);
cin>>n>>m;
rep(x,1,n+1){
p[x]=x;
s[x]=1;
}
int a,b;
int ans=0;
while (m--){
cin>>a>>b;
int A=par(a),B=par(b);
if (A!=B){
if (get(A,B)==-1) al[A].insert({B,IDX++});
auto it=al[A].lb(ii(B,-1));
int idx=(*it).se;
if (!id[idx].count(a)){
id[idx].insert(a);
num[B]++;
ans+=s[B];
}
if (get(B,A)!=-1) proc.pub({A,B});
}
while (!proc.empty()){
tie(A,B)=proc.back(); proc.pob();
A=par(A),B=par(B);
if (A==B) continue;
if (sz(al[A])+sz(al2[A])>sz(al[B])+sz(al2[B])) swap(A,B);
//update proc in case of more mergers
for (auto [it,idx]:al[A]) if (get(it,B)!=-1) proc.pub({A,it});
for (auto it:al2[A]) if (get(B,it)!=-1) proc.pub({A,it});
ans-=num[A]*s[A]+num[B]*s[B];
ans-=s[A]*(s[A]-1)+s[B]*(s[B]-1);
//erase same edges
int idx=get(A,B);
al[A].erase({B,idx});
al2[B].erase(A);
num[B]-=sz(id[idx]);
idx=get(B,A);
al[B].erase({A,idx});
al2[A].erase(B);
num[A]-=sz(id[idx]);
for (auto [it,idx]:al[A]){
int idx2=get(B,it);
al2[it].erase(A);
if (idx2==-1){
al[B].insert({it,idx});
al2[it].insert(B);
}
else{
if (sz(id[idx2])<sz(id[idx])) swap(id[idx2],id[idx]);
for (auto it:id[idx]) id[idx2].insert(it);
}
}
for (auto it:al2[A]){
int idx=get(it,A);
int idx2=get(it,B);
num[B]+=sz(id[idx]);
if (idx2==-1){
al[it].insert({B,idx});
al2[B].insert(it);
}
else{
if (sz(id[idx2])<sz(id[idx])) swap(id[idx2],id[idx]);
for (auto it:id[idx]){
if (id[idx2].count(it)) num[B]--;
else id[idx2].insert(it);
}
}
}
s[B]+=s[A];
ans+=num[B]*s[B];
ans+=s[B]*(s[B]-1);
p[A]=B;
}
//rep(x,1,n+1) cout<<p[x]<<" "; cout<<endl;
//rep(x,1,n+1) cout<<s[x]<<" "; cout<<endl;
//rep(x,1,n+1) cout<<num[x]<<" "; cout<<endl;
cout<<ans<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
23764 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
23764 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
23764 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
