CPP

c++ union set q5

class Solution {
private:
    vector<int> prnt1, prnt2;
    vector<int> rank1, rank2;
    
    int find(int u, vector<int> &prnt) {
        if(prnt[u] == -1)
            return u;
        return prnt[u] = find(prnt[u], prnt);
    }
    
    void merge(int u, int v, vector<int> &prnt, vector<int> &rank) {
        u = find(u, prnt);
        v = find(v, prnt);
        
        if(u == v) return;
        
        if(rank[u] < rank[v]) 
            swap(u, v);

        rank[u] += rank[v];
        prnt[v] = u;
    }
    
public:
    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
        prnt1.resize(n+1, -1);
        prnt2.resize(n+1, -1);
        
        rank1.resize(n+1, 1);
        rank2.resize(n+1, 1);
        
        int tot_t3 = 0, used_t3 = 0;
        for(auto it: edges) {
            if(it[0] != 3) 
                continue;
            tot_t3 += 1;
            if(find(it[1], prnt1) != find(it[2], prnt1)) {
                used_t3 += 1;
                merge(it[1], it[2], prnt1, rank1);
                merge(it[1], it[2], prnt2, rank2);
            }
        }
        
        int tot_t1 = 0, used_t1 = 0;
        int tot_t2 = 0, used_t2 = 0;
        for(auto it: edges) {
            if(it[0] == 1) {
                tot_t1 += 1;
                if(find(it[1], prnt1) != find(it[2], prnt1)) {
                    used_t1 += 1;
                    merge(it[1], it[2], prnt1, rank1);
                }
            } else if(it[0] == 2) {
                tot_t2 += 1;
                if(find(it[1], prnt2) != find(it[2], prnt2)) {
                    used_t2 += 1;
                    merge(it[1], it[2], prnt2, rank2);
                }
            }
        }
        
        if(used_t3 + used_t1 != n-1 || used_t3 + used_t2 != n-1)
            return -1;
        
        return (tot_t3 + tot_t2 + tot_t1) - (used_t3 + used_t2 + used_t1);
    }
};