✔💯 DAY 395 | DSU | 100% 0ms | [PYTHON/JAVA/C++] | EXPLAINED | Approach 🆙🆙🆙
Please Upvote as it really motivates me \uD83C\uDD99\uD83C\uDD99\uD83C\uDD99\n\n\n# Intuition \n##### \u2022\tWe have a graph with N nodes and bidirectional edg
# Please Upvote as it really motivates me \uD83C\uDD99\uD83C\uDD99\uD83C\uDD99\n\n![image.png](https://assets.leetcode.com/users/images/a2267944-10b8-41f2-b624-81a67ccea163_1680148646.205976.png)\n# Intuition \n##### \u2022\tWe have a graph with N nodes and bidirectional edges of three types: Type 1 (Alice only), Type 2 (Bob only), and Type 3 (both Alice and Bob).\n##### \u2022\tWe need to find the maximum number of edges that can be removed while still allowing both Alice and Bob to reach any node starting from any node via the remaining edges.\n##### \u2022\tWe can assume that there are two graphs, one for Alice and one for Bob, where the first graph has edges only of Type 1 and 3, and the second graph has edges only of Type 2 and 3.\n##### \u2022\tAn edge is useful only if it connects two nodes that are not already connected via some other edge or path.\n##### \u2022\tWe can use the Disjoint Set Union (DSU) data structure to detect if two nodes are connected via some path or not in O(\u03B1(N)), where \u03B1(N) is the extremely fast inverse Ackermann function.\n##### \u2022\tWe can use DSU to perform the union of two nodes for an edge, and if the nodes were not connected earlier (i.e., they have a different representative), then we know this edge is needed.\n##### \u2022\tFor every edge, if the two nodes were not connected earlier, we know this edge is required. To get the answer, we can subtract the number of required edges from the total number of edges.\n##### \u2022\tSince Type 3 edges are the most useful (as one Type 3 edge adds two edges, one for Alice and one for Bob), we will first iterate over the edges of Type 3 and add the edge to both graphs.\n##### \u2022\tIn the end, we need to check if the graph for both Alice and Bob is connected or not. If yes, we can say the edges that we didn\'t connect can be removed. To check if the individual graphs are connected, we will check if the number of components in the graph is 1 or not.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n##### \u2022\tDefine constants for edge types indices: TYPE U, V, ALICE, BOB, BOTH.\n##### \u2022\tDefine the maxNumEdgesToRemove function that takes in the number of nodes (n) and an array of edges (edges).\n##### \u2022\tMove all edges of type BOTH to the start of the array.\n##### \u2022\tCreate two UnionFind data structures, one for Alice and one for Bob.\n##### \u2022\tInitialize a variable added to 0.\n##### \u2022\tIterate over the edges and add them to the appropriate UnionFind data structure.\n##### \u2022\tIf the edge is of type BOTH, add it to both UnionFind data structures.\n##### \u2022\tIf the edge is of type ALICE, add it to the Alice UnionFind data structure.\n##### \u2022\tIf the edge is of type BOB, add it to the Bob UnionFind data structure.\n##### \u2022\tIf the two UnionFind data structures are united, return the number of edges that were not added (edges.length - added).\n##### \u2022\tIf both UnionFind data structures are not united, it is impossible to remove enough edges to make them united, so return -1.\n##### \u2022\tDefine the UnionFind class that takes in the number of elements (n).\n##### \u2022\tInitialize the parent array with n+1 elements and the groups variable to n.\n##### \u2022\tDefine the union function that takes in two elements (u and v) and returns 1 if they were not already in the same group, 0 otherwise.\n##### \u2022\tFind the parent of an element and perform path compression.\n##### \u2022\tDefine the isUnited function that checks if all elements are in the same group and returns true if they are, false otherwise.\n\n\n\n# Code\n```java []\nclass Solution {\n    // constants for the edge types indices\n    static final int \n        TYPE = 0, U = 1, V = 2,\n        ALICE = 1, BOB = 2, BOTH = 3;\n\n    public int maxNumEdgesToRemove(final int n, final int[][] edges) {\n        // Move all edges of type BOTH to the start of the array\n        for (int i = 0, j = edges.length - 1; i < j; ) {\n            if (edges[i][TYPE] == BOTH) {\n                ++i;\n                continue;\n            }\n            final var temp = edges[i];\n            edges[i] = edges[j];\n            edges[j] = temp;\n            --j;\n        }\n\n        // Create two UnionFind data structures, one for Alice and one for Bob\n        final UnionFind \n            aliceUf = new UnionFind(n), \n            bobUf = new UnionFind(n);\n        private int added = 0;\n\n        // Iterate over the edges and add them to the appropriate UnionFind data structure\n        for (final var edge : edges) {\n            final int type = edge[TYPE];\n            final int u = edge[U];\n            final int v = edge[V];\n\n            // Add the edge to both UnionFind data structures if it is of type BOTH\n            added += switch (type) {\n                case BOTH -> \n                    aliceUf.union(u, v) | bobUf.union(u, v);\n                case ALICE -> aliceUf.union(u, v);\n                default -> bobUf.union(u, v);\n            };\n\n            // If both UnionFind data structures are united, return the number of edges that were not added\n            if (aliceUf.isUnited() && bobUf.isUnited())\n                return edges.length - added;\n        }\n\n        // If both UnionFind data structures are not united, it is impossible to remove enough edges to make them united\n        return -1;\n    }\n}\n\nclass UnionFind {\n    static final int ZERO = 0;\n    final int[] parent;\n    int groups;\n\n    // Initialize the UnionFind data structure with n groups\n    UnionFind(final int n) {\n        parent = new int[n + 1];\n        groups = n;\n    }\n\n    // Union two elements and return 1 if they were not already in the same group, 0 otherwise\n    int union(final int u, final int v) {\n        final int uParent = find(u);\n        final int vParent = find(v);\n        if (uParent == vParent)\n            return 0;\n        parent[uParent] = vParent;\n        --groups;\n        return 1;\n    }\n\n    // Find the parent of an element and perform path compression\n    int find(final int v) {\n        if (parent[v] != ZERO)\n            return parent[v] = find(parent[v]);\n        return v;\n    }\n\n    // Check if all elements are in the same group\n    boolean isUnited() {\n        return groups == 1;\n    }\n}\n```\n\n```c++ []\nclass Solution {\nprivate:\n    // constants for the edge types indices\n    static constexpr int \n        TYPE = 0, U = 1, V =2,\n        ALICE = 1, BOB = 2, BOTH = 3;\n\npublic:\n    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {\n        // Move all edges of type BOTH to the end of the array\n        for (int i = 0, j = edges.size() - 1; i < j; ) {\n            if (edges[i][TYPE] == BOTH) {\n                ++i;\n                continue;\n            }\n            swap(edges[i], edges[j]);\n            --j;\n        }\n\n        // Create two UnionFind data structures, one for Alice and one for Bob\n        UnionFind alice_uf(n), bob_uf(n);\n        int added = 0;\n\n        // Iterate over the edges and add them to the appropriate UnionFind data structure\n        for (const auto& edge : edges) {\n            const int type = edge[TYPE];\n            const int u = edge[U];\n            const int v = edge[V];\n\n            // Add the edge to both UnionFind data structures if it is of type BOTH\n            added += (type == BOTH) ? \n                alice_uf.union_(u, v) | bob_uf.union_(u, v) :\n                (type == ALICE) ? alice_uf.union_(u, v) : bob_uf.union_(u, v);\n\n            // If both UnionFind data structures are united, return the number of edges that were not added\n            if (alice_uf.is_united() && bob_uf.is_united())\n                return edges.size() - added;\n        }\n\n        // If both UnionFind data structures are united, return the number of edges that were not added\n        if (alice_uf.is_united() && bob_uf.is_united())\n            return edges.size() - added;\n\n        // If both UnionFind data structures are not united, it is impossible to remove enough edges to make them united\n        return -1;\n    }\n};\n\nclass UnionFind {\nprivate:\n    vector<int> parent;\n    int groups;\n\npublic:\n    // Initialize the UnionFind data structure with n groups\n    UnionFind(int n) : parent(n + 1), groups(n) {\n        iota(parent.begin(), parent.end(), 0);\n    }\n\n    // Union two elements and return 1 if they were not already in the same group, 0 otherwise\n    int union_(int u, int v) {\n        const int uParent = find_(u);\n        const int vParent = find_(v);\n        if (uParent == vParent)\n            return 0;\n        parent[uParent] = vParent;\n        --groups;\n        return 1;\n    }\n\n    // Find the parent of an element and perform path compression\n    int find_(int v) {\n        if (parent[v] != v)\n            parent[v] = find_(parent[v]);\n        return parent[v];\n    }\n\n    // Check if all elements are in the same group\n    bool is_united() {\n        return groups == 1;\n    }\n};\n```\n```python []\nclass Solution:\n   # constants for the edge types indices\n    TYPE, U, V, ALICE, BOB, BOTH = range(6)\n\n    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n        # Move all edges of type BOTH to the end of the array\n        i, j = 0, len(edges) - 1\n        while i < j:\n            if edges[i][self.TYPE] == self.BOTH:\n                i += 1\n                continue\n            edges[i], edges[j] = edges[j], edges[i]\n            j -= 1\n\n        # Create two UnionFind data structures, one for Alice and one for Bob\n        alice_uf, bob_uf = UnionFind(n), UnionFind(n)\n        added = 0\n\n        # Iterate over the edges and add them to the appropriate UnionFind data structure\n        for edge in edges:\n            type_, u, v = edge[self.TYPE], edge[self.U], edge[self.V]\n\n            # Add the edge to both UnionFind data structures if it is of type BOTH\n            if type_ == self.BOTH:\n                added += alice_uf.union(u, v) | bob_uf.union(u, v)\n            elif type_ == self.ALICE:\n                added += alice_uf.union(u, v)\n            else:\n                added += bob_uf.union(u, v)\n\n            # If both UnionFind data structures are united, return the number of edges that were not added\n            if alice_uf.is_united() and bob_uf.is_united():\n                return len(edges) - added\n\n        # If both UnionFind data structures are not united, it is impossible to remove enough edges to make them united\n        if not alice_uf.is_united() or not bob_uf.is_united():\n            return -1\n\n        # If both UnionFind data structures are united, return the number of edges that were not added\n        return len(edges) - added\n\n\nclass UnionFind:\n    def __init__(self, n: int):\n        self.parent = list(range(n + 1))\n        self.groups = n\n\n    def union(self, u: int, v: int) -> int:\n        u_parent = self.find(u)\n        v_parent = self.find(v)\n        if u_parent == v_parent:\n            return 0\n        self.parent[u_parent] = v_parent\n        self.groups -= 1\n        return 1\n\n    def find(self, v: int) -> int:\n        if self.parent[v] != v:\n            self.parent[v] = self.find(self.parent[v])\n        return self.parent[v]\n\n    def is_united(self) -> bool:\n        return self.groups == 1\n```\n\n\n# Complexity\nTime Complexity:\n1 Moving all edges of type BOTH to the end of the array takes O(n) time.\n\nCreating two UnionFind data structures takes O(n) time.\nIterating over the edges takes O(m) time, where m is the number of edges.\nAdding an edge to a UnionFind data structure takes O(\u03B1(n)) time, where \u03B1(n) is the extremely fast inverse Ackermann function.\nChecking if both UnionFind data structures are united takes O(1) time.\nOverall, the time complexity of the code is O(m \u03B1(n)), where m is the number of edges and n is the number of nodes.\nSpace Complexity:\n\nCreating two UnionFind data structures takes O(n) space.\nCreating the parent array for the UnionFind data structures takes O(n) space.\nCreating the added variable takes O(1) space.\nOverall, the space complexity of the code is O(n).\n\n# Please Upvote as it really motivates me \uD83C\uDD99\uD83C\uDD99\uD83C\uDD99\n![BREUSELEE.webp](https://assets.leetcode.com/users/images/062630f0-ef80-4e74-abdb-302827b99235_1680054012.5054147.webp)\n![image.png](https://assets.leetcode.com/users/images/303fa18d-281d-49f0-87ef-1a018fc9a488_1681355186.0923774.png)\n\n\n# Please Upvote\uD83D\uDC4D\uD83D\uDC4D\nThanks for visiting my solution.\uD83D\uDE0A Keep Learning\nPlease give my solution an upvote! \uD83D\uDC4D \uD83C\uDD99\uD83C\uDD99\uD83C\uDD99\nhttps://leetcode.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/solutions/3468567/day-395-dsu-100-0ms-python-java-c-explained-approach/\nIt\'s a simple way to show your appreciation and\nkeep me motivated. Thank you! \uD83D\uDE0A\n\n
['Union Find', 'Python', 'C++', 'Java', 'Python3']