Easiest Striver DSU Template Explained ✅🏆
Max Number of Edges to Remove to Keep Graph Fully Traversable\n\n## Intuition\nTo solve the problem of determining the maximum number of edges we can remove whi
# Max Number of Edges to Remove to Keep Graph Fully Traversable\n\n## Intuition\nTo solve the problem of determining the maximum number of edges we can remove while still keeping the graph fully traversable by both Alice and Bob, we can utilize the Disjoint Set Union (DSU) data structure, also known as Union-Find. This data structure helps efficiently manage and merge sets.\n\n## Approach\n1. **Sort the edges**: \n   - Sort the edges in descending order based on their types so that type 3 edges (usable by both Alice and Bob) are processed first. This allows us to maximize shared edges, which helps in minimizing the total number of edges used.\n   \n2. **Initialize DSU for Alice and Bob**: \n   - Create two instances of the DSU, one for Alice and one for Bob. This allows us to manage their connected components separately.\n\n3. **Process edges**:\n   - Iterate through each edge and handle it based on its type:\n     - **Type 3 (shared) edges**: Attempt to add them to both Alice\'s and Bob\'s DSU. If the edge results in a cycle in either DSU (i.e., the two nodes of the edge are already connected), it means the edge is redundant and can be removed. Increment the `removedEdges` counter for each such edge.\n     - **Type 1 (Alice) edges**: Attempt to add them only to Alice\'s DSU. If the edge results in a cycle, it is redundant and can be removed. Increment the `removedEdges` counter for each such edge.\n     - **Type 2 (Bob) edges**: Attempt to add them only to Bob\'s DSU. If the edge results in a cycle, it is redundant and can be removed. Increment the `removedEdges` counter for each such edge.\n\n4. **Check connectivity**:\n   - After processing all edges, check if both Alice\'s and Bob\'s DSU are fully connected. This means checking if both DSUs have exactly one connected component spanning all nodes (i.e., all nodes are connected directly or indirectly).\n   - If both Alice\'s and Bob\'s graphs are fully connected, return the count of removed edges. If not, return -1 indicating it\'s not possible to make both graphs fully traversable using the given edges.\n\n## Complexity\n- **Time complexity**:\n  - Sorting the edges: \\(O(E \\log E)\\), where \\(E\\) is the number of edges.\n  - Union-Find operations: nearly \\(O(1)\\) per operation, due to path compression and union by size/rank. So, the overall complexity for processing the edges is \\(O(E \\cdot \\alpha(N))\\), where \\(\\alpha\\) is the inverse Ackermann function.\n\n- **Space complexity**:\n  - Storing the DSU data structures: \\(O(N)\\), where \\(N\\) is the number of nodes.\n\n## Code\n```cpp\nclass DisjointSet {\n    vector<int> parent, size;\npublic:\n    DisjointSet(int n) {\n        parent.resize(n + 1);\n        size.resize(n + 1);\n        for (int i = 0; i <= n; i++) {\n            parent[i] = i;\n            size[i] = 1;\n        }\n    }\n\n    int findUltimateParent(int node) {\n        if (node == parent[node])\n            return node;\n        return parent[node] = findUltimateParent(parent[node]);\n    }\n\n    bool unionBySize(int u, int v) {\n        int ulp_u = findUltimateParent(u);\n        int ulp_v = findUltimateParent(v);\n        if (ulp_u == ulp_v)\n            return false;\n        if (size[ulp_u] < size[ulp_v]) {\n            parent[ulp_u] = ulp_v;\n            size[ulp_v] += size[ulp_u];\n        } else {\n            parent[ulp_v] = ulp_u;\n            size[ulp_u] += size[ulp_v];\n        }\n        return true;\n    }\n};\n\nclass Solution {\npublic:\n    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {\n        sort(edges.begin(), edges.end(), [&](auto const &a, auto const &b) {\n            return a[0] > b[0];\n        });\n\n        DisjointSet dsAlice(n);\n        DisjointSet dsBob(n);\n\n        int removedEdges = 0, aliceEdges = 0, bobEdges = 0;\n        for (auto edge : edges) {\n            if (edge[0] == 3) {\n                if (dsAlice.unionBySize(edge[1], edge[2])) {\n                    dsBob.unionBySize(edge[1], edge[2]);\n                    aliceEdges++;\n                    bobEdges++;\n                } else {\n                    removedEdges++;\n                }\n            } else if (edge[0] == 2) {\n                if (dsBob.unionBySize(edge[1], edge[2])) {\n                    bobEdges++;\n                } else {\n                    removedEdges++;\n                }\n            } else {\n                if (dsAlice.unionBySize(edge[1], edge[2])) {\n                    aliceEdges++;\n                } else {\n                    removedEdges++;\n                }\n            }\n        }\n        return (bobEdges == n - 1 && aliceEdges == n - 1) ? removedEdges : -1;\n    }\n};\n
['Union Find', 'Graph', 'C++']