DIS-JOINTSET UNION | EASY | ✅✅ | IMPLEMENTATION |
Intuition\n- Using 2 separete disjoint set for both alice and bob.\n\n# Approach\n- Sort the edges.\n- First process type 3 edges and then connect u, v and incr
# Intuition\n- Using 2 separete disjoint set for both alice and bob.\n\n# Approach\n- Sort the edges.\n- First process type 3 edges and then connect u, v and increment the count if they have not unioned before\n- Simillarly process type 2 and type 1 edges and incremen the count of alice and bob and overall count.\n- if alice and bob != n - 1 return -1\n- else return edge.sz() - count\n\n\n# Code\n```\nclass DSU {\n\tvector<int>parent, size;\npublic:\n\n\tDSU(int n) {\n        size.resize(n + 1, 0);\n\t\tparent.resize(n + 1, 0);\n\t\tfor(int i = 0; i <= n; i++) {\n\t\t\tparent[i] = i;\n\n\t\t}\n\t}\n\n\tbool isSame(int u, int v) {\n        return findPar(u) == findPar(v);\n    }\n\t\n\tint findPar(int node) {\n\t\tif(node == parent[node]) return node;\n\t\treturn parent[node] = findPar(parent[node]);\n\t}\n\n\tint unionBySize(int u, int v) {\n\t\tint ulp_u = findPar(u);\n\t\tint ulp_v = findPar(v);\n\t\tif(ulp_u == ulp_v) return 0;\n\t\tif(size[ulp_u] < size[ulp_v]) {\n\t\t\tparent[ulp_u] = ulp_v;\n\t\t\tsize[ulp_v] += size[ulp_u];\n\t\t} \n\t\telse {\n\t\t\tparent[ulp_v] = ulp_u;\n\t\t\tsize[ulp_u] += size[ulp_v];\n\t\t}\n        return 1;\n\t}\n};\n\n\nclass Solution {\npublic:\n    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {\n\n        DSU d1(n);\n        DSU d2(n);\n\n        int alice = 0, bob = 0, c = 0;\n\n        sort(edges.rbegin(), edges.rend());\n\n        for(auto it : edges) {\n            int t = it[0], u = it[1], v = it[2];\n\n            if(t == 3) {\n                int f1 = d1.unionBySize(u, v);\n                int f2 = d2.unionBySize(u, v);\n                alice += f1;\n                bob += f2;\n                if(f1 | f2) c++;\n            }\n            else if(t == 2) {\n                int f2 = d2.unionBySize(u, v);\n                bob += f2;\n                c += f2;\n            }\n            else {\n                int f1 = d1.unionBySize(u, v);\n                alice += f1;\n                c += f1;\n            }\n        }\n\n        if(alice != n- 1 || bob != n - 1) return -1;\n\n        return edges.size() - c;\n    }\n};\n```
['Union Find', 'C++']