C++ || Union Find || using striver's template
Approach\n1. We have to find the maximum number of edges that can be removed from the graph while ensureing that both Alice and Bob able to construct a spanning
**Approach**\n1. We have to find the maximum number of edges that can be removed from the graph while ensureing that both Alice and Bob able to construct a spanning tree. As spanning tree connects all the nodes in a graph, all nodes will be traversable in that case. we also know that there must be n-1 edges in the spanning tree.\n2. We can use the union-find data structure to keep track of which nodes are connected to each other in the spanning tree, so we have defined two dsu\'s for alice and bob. Initially, each node is its own parent. Also we defined alice_edge, bob_edge to track no of edges in their spanning tree and removed_edge for counting no of removable edges.\n3. At first we start by considering the edges that can be used by both Alice and Bob i.e. type 3 edges. Because If we can merge the two nodes of type 3 edge it contributes in construction of both alice and bobs spanning tree. so increase the count of edges of boths dsu\'s [alice_edge, bol_edge]. If not possible to merge them, it means they are already connected so the current edge is redundent and we can remove it.\n4. Next, we consider the edges that can only be used by Alice and Bob respectively. If a type 1 or type 2 edge can be used to connect two nodes in Alice\'s or Bob\'s respective connected components, then we know that only that user can use that edge to construct their spanning tree so increase their respcetive edge count. Otherwise, remove the edge same as type 3.\n5. Finally, check if both Alice and Bob were able to construct a spanning tree (i.e. they both have n-1 no of edges). If that possible then we can return the no of removed edge [removed_edge]. else return -1.\n\n**Disjoint Set  class**\n```\nclass DisjointSet {\n    vector<int> parent; \n    vector<int> rank;\n    public:\n    DisjointSet(int n) {\n        parent.resize(n+1,0);\n        rank.resize(n+1,0);\n        \n        for(int i = 0; i < n; i++) {\n            parent[i] = i;\n            rank[i] = 1;\n        }\n    }\n    \n    int findUParent(int node) {\n        if(node == parent[node])\n            return node;\n        return parent[node] = findUParent(parent[node]);\n    }\n    \n    void unionByRank(int u, int v) {\n        int uparentU = findUParent(u);\n        int uparentV = findUParent(v);\n        \n        if(rank[uparentU] > rank[uparentV]) {\n            parent[uparentV] = uparentU;\n\n        } else if(rank[uparentU] < rank[uparentV]){\n            parent[uparentU] = uparentV;\n\n        } else {\n            parent[uparentU] = uparentV;\n            rank[uparentV]++;\n        }       \n    }\n};\n```\n\n**Solution Class**\n```\nclass Solution {\npublic:\n    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {\n        DisjointSet alice(n), bob(n);\n        \n        int removed_edge = 0, alice_edge = 0, bob_edge = 0;\n        \n        for(auto edge : edges) {\n            if(edge[0] == 3) {\n                if(alice.findUParent(edge[1]) != alice.findUParent(edge[2])) {\n                    alice.unionByRank(edge[1], edge[2]);\n                    bob.unionByRank(edge[1], edge[2]);\n                    alice_edge++;\n                    bob_edge++;\n                } else {\n                    removed_edge++;\n                }\n            }\n        }\n            \n         for(auto edge : edges) {\n            if(edge[0] == 2) {\n                if(bob.findUParent(edge[1]) != bob.findUParent(edge[2])) {\n                    bob.unionByRank(edge[1], edge[2]);\n                    bob_edge++;\n                } else {\n                    removed_edge++;\n                }\n            } else if(edge[0] == 1) {\n                if(alice.findUParent(edge[1]) != alice.findUParent(edge[2])) {\n                    alice.unionByRank(edge[1], edge[2]);\n                    alice_edge++;\n                } else {\n                    removed_edge++;\n                }\n            }\n        }  \n        \n        return (alice_edge == n-1 && bob_edge == n-1) ? removed_edge : -1;\n    }\n};\n```\n\n**TC : O(N)** [as we are using two loops and union find takes O(4\u03B1) which is approximately O(1)]\n**SC: O(N)** [as we taking two dsu objects means toatal 4 arrays i.e. O(N)]\n\n**Please upvote if you like the solution !!\uD83D\uDE0A**
['Union Find', 'Graph', 'C']