C++ DSU Application beats around 97% runtime
We give priority to third type of paths first. Essentially, we are connecting the nodes of different paths as seperate components and then adding/selecting edge
We give priority to third type of paths first. Essentially, we are connecting the nodes of different paths as seperate components and then adding/selecting edges to connect them. \n```\nclass Solution {\npublic:\n    vector<int> par, rank ; \n    \n    int find(int v){\n        if(par[v] == v)\n            return v ; \n        return par[v] = find(par[v]) ; \n    }\n    \n    void unionfn(int a, int b) {\n        a = find(a) ; \n        b = find(b) ; \n        if(a!=b) {\n            if(rank[a] < rank[b])\n                swap(a, b) ; \n            par[b] = a ; \n            if(rank[b] == rank[a])\n                rank[a]++ ; \n        }\n    }\n    \n    int calc(int type, vector<vector<int>>& e) {\n        int ct = 0 ; \n        for(int i = 0 ; i < e.size() ; i++) {\n            if(e[i][0] == type and find(e[i][1]) != find(e[i][2])) {\n                ct++ ; \n                unionfn(e[i][1], e[i][2]) ; \n            }\n        }\n        return ct ; \n    }\n    \n    int maxNumEdgesToRemove(int n, vector<vector<int>>& e) {\n        rank.assign(n+1, 0) ;  \n        for(int i =0 ; i <= n ; i++)\n            par.push_back(i) ; \n        int common = calc(3, e) ; \n        vector<int> temp = par ; \n        int alice = calc(1, e) ; \n        par = temp ; \n        int bob = calc(2, e) ; \n        if((common + alice != n-1) or (common + bob != n-1))\n            return -1 ; \n        return (e.size()-common-alice-bob) ; \n    }\n};\n```
['Union Find', 'C']