We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
#include<bits/stdc++.h>#define ll unsigned long long int#define MAX 10e5+5usingnamespacestd;vector<int>parent(MAX);vector<int>no_of_friends(MAX);llfindparent(intx){if(parent[x]==x)returnx;returnparent[x]=findparent(parent[x]);}llvalue(lln){llt1=n*(n+1)*(2*n+1);t1/=6;llt2=n*(n+1);t2/=2;returnt1-t2;}intmain(){intq;cin>>q;while(q--){lln,m;cin>>n>>m;llTotal=0;llcurrent=0;llans=0;for(lli=1;i<=n;i++){parent[i]=i;no_of_friends[i]=1;}for(lli=0;i<m;i++){llu,v;cin>>u>>v;llpu=findparent(u);llpv=findparent(v);if(pu!=pv){parent[pv]=pu;no_of_friends[pu]+=no_of_friends[pv];}}vector<ll>p;for(lli=1;i<=n;i++){if(parent[i]==i)p.push_back(no_of_friends[i]);}sort(p.begin(),p.end(),greater<ll>());for(lli=0;i<p.size();i++){//cout<<p[i]<<endl;current+=(p[i]-1);ans+=value(p[i])+Total*(p[i]-1);//cout<<ans<<endl;Total+=(p[i]*(p[i]-1));}// cout<<m<<" "<<Total<<endl;ans+=((m-current)*Total);cout<<ans<<endl;}}
The Value of Friendship
You are viewing a single comment's thread. Return to all comments →