In this HackerEarth A fair competition problem solution In competition, N participants are competing against each other for the top two spots. There are M friendly relations between participants. In each friendship relation, you will be given two integers L and R, indicating L and R are friends.
HackerEarth A fair competition problem solution.
#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
#define endl "n"
#define test ll txtc; cin>>txtc; while(txtc--)
typedef long long int ll;
typedef long double ld;
class dsu{
public:
vector<ll>par;
vector<ll>sz;
dsu(ll n){
par.resize(n);
iota(par.begin(),par.end(),0);
sz.assign(n,1);
}
ll get(ll x){
return (par[x]==x?x:(par[x]=get(par[x])));
}
bool unite(ll x,ll y){
x=get(x);
y=get(y);
if(x!=y){
sz[y]+=sz[x];
sz[x]=0;
par[x]=y;
return true;
}
return false;
}
};
ll calc(ll n){
if(n<=1) return 0;
ll ans=n*(n-1);
return ans;
}
int main() {
FIO;
test
{
ll n,m,l,r,ans=0; cin>>n>>m;
dsu d(n);
vector<ll>adj[n];
for(ll i=0;i<m;i++){
cin>>l>>r; l--; r--;
bool ok=d.unite(l,r);
}
ans=calc(n);
for(ll i=0;i<n;i++){
ans-=calc(d.sz[i]);
}
cout<<ans<<endl;
}
return 0;
}
Second solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 14;
struct Dsu{
int par[maxn];
Dsu(){ memset(par, -1, sizeof par); }
int root(int v){
return par[v] < 0 ? v : par[v] = root(par[v]);
}
bool fri(int v, int u){
return root(v) == root(u);
}
bool merge(int v, int u){
if((v = root(v)) == (u = root(u)))
return 0;
par[u] += par[v];
par[v] = u;
return 1;
}
} dsu;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int t;
cin >> t;
while(t--) {
int n, m;
cin >> n >> m;
dsu = Dsu();
for (int i = 0; i < m; ++i) {
int v, u;
cin >> v >> u;
dsu.merge(--v, --u);
}
ll ans = n * ll(n - 1);
for (int i = 0; i < n; ++i) {
if (dsu.par[i] < 0)
ans -= dsu.par[i] * ll(dsu.par[i] + 1);
}
cout << ans << 'n';
}
}