Easy Explained Solution with comments||C++||Java
Approach\n### DisjointSet Class Explanation\n\nThe DisjointSet class manages a collection of disjoint sets using two primary arrays: Parent and Rank. The Parent
# Approach\n### DisjointSet Class Explanation\n\nThe `DisjointSet` class manages a collection of disjoint sets using two primary arrays: `Parent` and `Rank`. The `Parent` array keeps track of the parent node for each element, while the `Rank` array helps to keep the tree flat by attaching smaller trees under the root of larger trees. The constructor initializes each node to be its own parent and sets the initial rank to zero. The `FindUltimateParent` method uses path compression to ensure that each node directly points to the root of its set, improving the efficiency of future queries. The `UnionByRank` method merges two sets by rank, ensuring that the tree remains balanced. The `isSingleComponent` method checks if all nodes are connected into a single component by verifying if there is only one component left.\n\n### Solution Class Explanation\n\nThe `Solution` class contains the `maxNumEdgesToRemove` method, which aims to maximize the number of removable edges while ensuring both Alice and Bob can still traverse the entire graph.\n\n1. **Edge Sorting:** Edges are sorted in descending order based on their type. Type 3 edges (usable by both Alice and Bob) are processed first, followed by type 2 (only for Bob) and type 1 (only for Alice). This ensures that edges which are most beneficial (type 3) are considered first.\n\n2. **Disjoint Sets for Alice and Bob:** Two separate `DisjointSet` instances are created for Alice and Bob to manage their respective graphs.\n\n3. **Processing Edges:** The method iterates over the sorted edges:\n   - **Type 3 Edges:** If the edge connects two different components for either Alice or Bob, it is used and the components are united. The `edgeCount` is incremented if the edge is used by either Alice or Bob.\n   - **Type 2 Edges:** If the edge connects two different components for Bob, it is used and the components are united. The `edgeCount` is incremented if the edge is used.\n   - **Type 1 Edges:** If the edge connects two different components for Alice, it is used and the components are united. The `edgeCount` is incremented if the edge is used.\n\n4. **Checking Connectivity:** After processing all edges, the method checks if both Alice and Bob\'s graphs are fully connected using the `isSingleComponent` method. If both graphs are connected, the number of removable edges is calculated by subtracting `edgeCount` from the total number of edges. If either graph is not fully connected, the method returns `-1` to indicate that it\'s impossible to ensure full traversal for both Alice and Bob with the given edges.\n\n# Complexity\n### Space Complexity\n\n1. **DisjointSet Class:**\n   - **Parent and Rank Arrays:** Each array has a size of \\(n + 1\\), where \\(n\\) is the number of nodes. Thus, the space complexity for these arrays is \\(O(n)\\).\n   - **Components Variable:** This is an integer variable, so it has a space complexity of \\(O(1)\\).\n\n   Overall, the space complexity of the `DisjointSet` class is \\(O(n)\\).\n\n2. **Solution Class:**\n   - **Edges Storage:** The `edges` vector stores all the edges, and its space complexity is \\(O(E)\\), where \\(E\\) is the number of edges.\n   - **Disjoint Sets for Alice and Bob:** Each `DisjointSet` instance requires \\(O(n)\\) space. Since there are two instances (one for Alice and one for Bob), this contributes \\(O(n) + O(n) = O(n)\\) space.\n\n   Overall, the space complexity of the `Solution` class is \\(O(n + E)\\).\n\n### Time Complexity\n\n1. **DisjointSet Class:**\n   - **FindUltimateParent:** The amortized time complexity of the `FindUltimateParent` method with path compression is \\(O(\\alpha(n))\\), where \\(\\alpha\\) is the inverse Ackermann function, which grows very slowly and is nearly constant for practical purposes.\n   - **UnionByRank:** The time complexity for the `UnionByRank` method is \\(O(\\alpha(n))\\).\n\n2. **Solution Class:**\n   - **Edge Sorting:** Sorting the edges takes \\(O(E \\log E)\\) time.\n   - **Processing Each Edge:** For each edge, the `FindUltimateParent` and `UnionByRank` operations are performed. Each of these operations takes \\(O(\\alpha(n))\\) time. Since there are \\(E\\) edges, the total time for processing edges is \\(O(E \\cdot \\alpha(n))\\).\n\n   Overall, the time complexity of the `maxNumEdgesToRemove` method is dominated by the sorting step and the processing of the edges, resulting in \\(O(E \\log E + E \\cdot \\alpha(n))\\). Given that \\(\\alpha(n)\\) is nearly constant, this can be simplified to \\(O(E \\log E)\\) for practical purposes.\n\n# Code\n```\nclass DisjointSet\n{\npublic:\n    vector<int> Parent;  // To store the parent of each node\n    vector<int> Rank;    // To store the rank (or depth) of each tree\n    int components;      // To keep track of the number of components\n\n    // Constructor\n    DisjointSet(int n)\n    {\n        Rank.resize(n + 1, 0);  // Initialize rank to 0 for all nodes\n        Parent.resize(n + 1);   // Initialize parent array\n        components = n;         // Initially, each node is its own component\n        for (int i = 0; i <= n; i++)\n        {\n            Parent[i] = i;      // Each node is its own parent initially\n        }\n    }\n\n    // Function to find the ultimate parent of a node with path compression\n    int FindUltimateParent(int node)\n    {\n        if (node == Parent[node])  // If the node is its own parent, return the node\n        {\n            return node;\n        }\n        return (Parent[node] = FindUltimateParent(Parent[node]));  // Path compression\n    }\n\n    // Union by rank\n    void UnionByRank(int u, int v)\n    {\n        int Ult_U = FindUltimateParent(u);  // Find the ultimate parent of u\n        int Ult_V = FindUltimateParent(v);  // Find the ultimate parent of v\n\n        // If both nodes belong to the same component, do nothing\n        if (Ult_U == Ult_V)\n        {\n            return;\n        }\n\n        // Else, unite the components\n        if (Rank[Ult_U] < Rank[Ult_V])\n        {\n            Parent[Ult_U] = Ult_V;  // Attach the tree with smaller rank to the root of the tree with larger rank\n        }\n        else if (Rank[Ult_U] > Rank[Ult_V])\n        {\n            Parent[Ult_V] = Ult_U;  // Attach the tree with smaller rank to the root of the tree with larger rank\n        }\n        else\n        {\n            Parent[Ult_V] = Ult_U;  // If ranks are equal, make one the parent and increase its rank\n            Rank[Ult_U]++;\n        }\n        components--;  // Decrease the component count since two components have been united\n    }\n\n    // Function to check if all nodes are in a single component\n    bool isSingleComponent()\n    {\n        return components == 1;\n    }\n};\n\nclass Solution {\nprivate:\n    // Comparator function to sort edges\n    static bool cmp(vector<int>&a, vector<int>&b)\n    {\n        return a[0] < b[0];\n    }\n\npublic:\n    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {\n        // Sort edges by type in descending order (type 3 first, then type 2, and type 1 last)\n        sort(edges.rbegin(), edges.rend(), cmp);\n\n        DisjointSet alice(n);  // Disjoint set for Alice\n        DisjointSet bob(n);    // Disjoint set for Bob\n\n        int edgeCount = 0;     // Count of edges used\n\n        for (auto &it : edges)\n        {\n            int type = it[0];\n            int u = it[1];\n            int v = it[2];\n\n            if (type == 3)\n            {\n                bool flag = false;\n\n                // For Alice\n                if (alice.FindUltimateParent(u) != alice.FindUltimateParent(v))\n                {\n                    alice.UnionByRank(u, v);\n                    flag = true;\n                }\n\n                // For Bob\n                if (bob.FindUltimateParent(u) != bob.FindUltimateParent(v))\n                {\n                    bob.UnionByRank(u, v);\n                    flag = true;\n                }\n                if (flag)\n                {\n                    edgeCount++;  // If the edge was used by either Alice or Bob, increase the count\n                }\n            }\n            else if (type == 2)\n            {\n                bool flag = false;\n\n                // For Bob\n                if (bob.FindUltimateParent(u) != bob.FindUltimateParent(v))\n                {\n                    bob.UnionByRank(u, v);\n                    flag = true;\n                }\n                if (flag)\n                {\n                    edgeCount++;  // If the edge was used by Bob, increase the count\n                }\n            }\n            else\n            {\n                bool flag = false;\n\n                // For Alice\n                if (alice.FindUltimateParent(u) != alice.FindUltimateParent(v))\n                {\n                    alice.UnionByRank(u, v);\n                    flag = true;\n                }\n                if (flag)\n                {\n                    edgeCount++;  // If the edge was used by Alice, increase the count\n                }\n            }\n        }\n\n        // If both Alice and Bob can traverse the entire graph, return the number of edges that can be removed\n        if (alice.isSingleComponent() && bob.isSingleComponent())\n        {\n            return edges.size() - edgeCount;  // Total edges minus used edges gives the removable edges\n        }\n        return -1;  // If not, return -1 indicating it\'s not possible\n    }\n};\n\n```
['Union Find', 'Graph', 'C++']