🌟C++ || DSU || Explained with detailed approach
Intuition\nQuite a simple logic to solve this particular problem\n1. Intially sort the edges in descending order of their typessuch that the type 3 edges get th
# Intuition\n***Quite a simple logic to solve this particular problem***\n1. Intially sort the edges in descending order of their typessuch that the type 3 edges get the highest priority\n2. Then simple create 2 objects one for Alice and one for Bob\n3. These DSU objects can be used to check whether both alice and bob can traverse the entire graph.\n4. Now start iterating the edges :- \n    4.1 if the edge is type 3 : add that edge for Alice and Bob;\n    4.2 if the edge is type 2 : add the edge to the Bob object;\n    4.3 if the edge is type 1 : add the edge to the Alice object;\n5. At the end check whether both Alice and Bob can traverse the Entire Graph\n\n# Code\n```\nclass dsu{\nprivate:\n    vector<int>parent;\n    int distinct_components;\npublic:\n    \n    dsu(int n){\n        distinct_components = n;\n\n        for(int i=0;i<=n;i++){\n            parent.push_back(i);\n        }\n    }\n    int find_parent(int u){\n        if(parent[u] != u){\n            parent[u] = find_parent(parent[u]);\n        }\n        return parent[u];\n    }\n    bool Union(int u, int v){\n        if(find_parent(u) == find_parent(v)){\n            return false;\n        }\n\n        parent[find_parent(u)] = v;\n        distinct_components--;\n        return true;\n    }\n    bool united(){\n        return distinct_components == 1;\n    }\n};\n\nclass Solution {\npublic:\n    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {\n\n        sort(edges.begin(),edges.end(), [](auto& it, auto &it2){\n            return it[0] > it2[0];\n        });\n\n        dsu *bob = new dsu(n);\n        dsu *alice = new dsu(n);\n        int edges_added = 0;\n\n        for(auto &it : edges){\n            int type = it[0];\n            int u = it[1];\n            int v = it[2];\n\n            switch(type){\n                case 3 : {\n                    edges_added += (bob->Union(u,v) | alice->Union(u,v));\n                    break;\n                }\n                case 2:{\n                    edges_added += bob->Union(u,v);\n                    break;\n                }\n                case 1 : {\n                    edges_added += alice->Union(u,v);\n                    break;\n                }\n            }\n        }\n\n        return (bob->united() && alice->united()) ? edges.size() - edges_added : -1;\n    }\n};\n\n\n\n\n\n\n\n\n```
['C++']