HackerEarth A fair competition problem solution

YASH PAL, 31 July 202414 February 2026

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

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';
    }
}

coding problems solutions HackerEarth HackerEarth

Leave a Reply