The director of your college is planning to send 2 people to the ICPC regionals. He wants them to be from different branches. You will be given a list of pairs of student ids. Each pair is made of students from the same branch. Determine how many pairs of students from different branches they can choose from. Example 1: Input: N=5 P=3 pairs[]={{…

To Count pairs using rank in DSU

class Solution {
    public:
    vector<int>par;
    vector<int>rank;
    int find(int a){
        return par[a] == a?a:par[a] = find(par[a]);
    }
    void unin(int a,int b)
    {
        if(a == b)return;
        if(rank[a]<rank[b]){
            rank[b]+=rank[a];
            rank[a] = 0;
            par[a] = b;
        }else{
            rank[a]+=rank[b];
            rank[b] = 0;
            par[b] = a;
        }
    }
        long long int numberOfPairs(vector<vector<int>> &pairs,int p,int n)
        {
            par.clear();
            par.resize(n);
            rank.clear();
            rank.resize(n,1);
            iota(par.begin(),par.end(),0);
            for(auto a:pairs){
                unin(find(a[0]),find(a[1]));
            }
            long long int ans=0;
        
        // to count no of pairs
        for(int i=n-2;i>=0;i--){
            ans+= rank[i]*rank[i+1];
            rank[i]+= rank[i+1];
        }
        return ans;
            // code here
        }
};
// url :- https://practice.geeksforgeeks.org/problems/number-of-pairs-1645358985/1/?page=1&status[]=unsolved&curated[]=7&sortBy=submissions#