✅Beats 100% -Explained with [ Video ] -C++/Java/Python/JS - Union Find
\n\n\n# YouTube Video Explanation:\n\n ### To watch the video please click on "Watch On Youtube" option  available the left bottom corner of the thumbnail. \n\n
![Screenshot 2024-06-30 083946.png](https://assets.leetcode.com/users/images/cd16ddc0-22c8-481a-8203-30fe3a533302_1719717922.4483893.png)\n\n\n# YouTube Video Explanation:\n\n<!-- ### To watch the video please click on "Watch On Youtube" option  available the left bottom corner of the thumbnail. -->\n\n<!-- **If you want a video for this question please write in the comments** -->\n\n\nhttps://youtu.be/LfaQjcE_LEM\n\n# The video doesn\'t have the code part today due to some failure. Please watch it from the solution below. Sorry for it.\n\n\n**\uD83D\uDD25 Please like, share, and subscribe to support our channel\'s mission of making complex concepts easy to understand.**\n\nSubscribe Link: https://www.youtube.com/@leetlogics/?sub_confirmation=1\n\n*Subscribe Goal: 2400 Subscribers*\n*Current Subscribers: 2357*\n\nFollow me on Instagram : https://www.instagram.com/divyansh.nishad/\n\n---\n\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo solve this problem, we need to ensure that both Alice and Bob can traverse the entire graph independently. This can be achieved by ensuring each has a connected graph (spanning tree). Using the Union-Find data structure, we can efficiently manage the connectivity of the graph. The goal is to maximize the number of edges removed while ensuring both Alice and Bob can still traverse all nodes.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Initialize Union-Find Structures**: Create two separate Union-Find structures, one for Alice and one for Bob, to manage their connectivity.\n2. **Process Type 3 Edges First**: Type 3 edges are the most valuable because they can be used by both Alice and Bob. We iterate through these edges first and attempt to add them to both Alice\'s and Bob\'s graphs. If the edge successfully connects two previously unconnected components for either Alice or Bob, it is necessary.\n3. **Process Type 1 and Type 2 Edges**: After handling type 3 edges, we separately process type 1 edges for Alice and type 2 edges for Bob. These edges are only useful if they connect new components for Alice or Bob, respectively.\n4. **Check Full Connectivity**: After processing all edges, we check if both Alice\'s and Bob\'s graphs are fully connected.\n5. **Calculate Removable Edges**: The number of removable edges is the total number of edges minus the number of edges required to ensure full connectivity for both Alice and Bob.\n\n# Complexity\n- **Time Complexity**: \n  - The Union-Find operations (find and union) are nearly constant time due to path compression and union by rank. \n  - Processing all edges involves iterating through them twice, giving a complexity of \\(O(E)\\), where \\(E\\) is the number of edges.\n- **Space Complexity**: \n  - We use extra space for the Union-Find data structures, each requiring \\(O(N)\\) space for representative and component size arrays, where \\(N\\) is the number of nodes.\n\n\n# Explanation\n\n1. **Initialization**:\n    - Create two Union-Find instances: one for Alice and one for Bob.\n    - Initialize the number of edges required to be included in the graph (`edgesRequired`).\n\n    | Variable        | Description                                         |\n    |-----------------|-----------------------------------------------------|\n    | `alice`         | Union-Find instance for Alice                       |\n    | `bob`           | Union-Find instance for Bob                         |\n    | `edgesRequired` | Counter for edges that are required in the graph    |\n\n2. **Processing Type 3 Edges**:\n    - First, include all type 3 edges, which can be used by both Alice and Bob.\n\n    | Edge Type | Operation                                                   |\n    |-----------|-------------------------------------------------------------|\n    | Type 3    | Try to union nodes in both `alice` and `bob` Union-Find     |\n    |           | If successful in either, increment `edgesRequired`          |\n\n3. **Processing Type 1 and Type 2 Edges**:\n    - Process remaining edges: type 1 (Alice) and type 2 (Bob).\n\n    | Edge Type | Operation                                                   |\n    |-----------|-------------------------------------------------------------|\n    | Type 1    | Try to union nodes in `alice` Union-Find                    |\n    |           | If successful, increment `edgesRequired`                    |\n    | Type 2    | Try to union nodes in `bob` Union-Find                      |\n    |           | If successful, increment `edgesRequired`                    |\n\n4. **Final Check**:\n    - Ensure both Alice and Bob can fully traverse the graph by checking if their respective Union-Find structures are fully connected.\n\n    | Condition                                | Action                          |\n    |------------------------------------------|---------------------------------|\n    | Both `alice` and `bob` are connected     | Return `len(edges) - edgesRequired` |\n    | Either `alice` or `bob` is not connected | Return `-1`                         |\n\n#### Example Walkthrough\n\n**Example Input**:\n```python\nn = 4\nedges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]\n```\n\n**Processing Steps**:\n\n1. **Initialize**:\n    - `alice` and `bob` Union-Find instances.\n    - `edgesRequired = 0`.\n\n2. **Type 3 Edges**:\n    - Process `[3,1,2]`:\n        - Union nodes 1 and 2 in both `alice` and `bob`.\n        - Increment `edgesRequired` to 1.\n    - Process `[3,2,3]`:\n        - Union nodes 2 and 3 in both `alice` and `bob`.\n        - Increment `edgesRequired` to 2.\n\n3. **Type 1 and Type 2 Edges**:\n    - Process `[1,1,3]` for `alice`:\n        - Union nodes 1 and 3.\n        - Increment `edgesRequired` to 3.\n    - Process `[1,2,4]` for `alice`:\n        - Union nodes 2 and 4.\n        - Increment `edgesRequired` to 4.\n    - Process `[1,1,2]` for `alice`:\n        - Union not needed (already connected), no increment.\n    - Process `[2,3,4]` for `bob`:\n        - Union nodes 3 and 4.\n        - Increment `edgesRequired` to 5.\n\n4. **Final Check**:\n    - Both `alice` and `bob` Union-Find structures are fully connected.\n    - Total edges: 6, edges required: 5.\n    - Edges removed: `6 - 5 = 1`.\n\n**Output**:\n```python\n1\n```\n\n# Code\n```java []\nclass Solution {\n    public int maxNumEdgesToRemove(int n, int[][] edges) {\n        UnionFind alice = new UnionFind(n);\n        UnionFind bob = new UnionFind(n);\n\n        \n        int edgesRequired = 0;\n        for(int[] edge : edges) {\n            if(edge[0]==3) {\n                edgesRequired+= (alice.preformUnion(edge[1], edge[2]) | bob.preformUnion(edge[1], edge[2]));\n            }\n        }\n\n        for(int[] edge : edges) {\n            if(edge[0]==2) {\n                edgesRequired += bob.preformUnion(edge[1], edge[2]);\n            } else if(edge[0]==1) {\n                edgesRequired += alice.preformUnion(edge[1], edge[2]);\n            }\n        }\n\n        if(alice.isConnected() && bob.isConnected()) {\n            return edges.length - edgesRequired;\n        }\n\n        return -1;\n\n    }\n\n    class UnionFind {\n\n        int[] representative;\n        int[] componentSize;\n        int components;\n\n        UnionFind(int n) {\n            components = n;\n            representative = new int[n+1];\n            componentSize = new int[n+1];\n\n            for(int i=0;i<=n;i++) {\n                representative[i] = i;\n                componentSize[i] = i;\n            }\n        }\n\n        int findRepresentative(int x) {\n            if(representative[x] == x) {\n                return x;\n            }\n\n            return representative[x] = findRepresentative(representative[x]);\n        }\n\n        int preformUnion(int x, int y) {\n            x = findRepresentative(x); y = findRepresentative(y);\n\n            if(x==y) {\n                return 0;\n            }\n\n            if(componentSize[x]>componentSize[y]) {\n                componentSize[x]+=componentSize[y];\n                representative[y] = x;\n            } else {\n                componentSize[y]+=componentSize[x];\n                representative[x] = y;\n            }\n\n            components--;\n            return 1;\n        }\n\n        boolean isConnected() {\n            return components==1;\n        }\n    }    \n}\n```\n```C++ []\nclass Solution {\npublic:\n    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {\n        class UnionFind {\n        public:\n            vector<int> parent, size;\n            int components;\n            UnionFind(int n) {\n                components = n;\n                parent.resize(n + 1);\n                size.resize(n + 1, 1);\n                for (int i = 0; i <= n; ++i) {\n                    parent[i] = i;\n                }\n            }\n\n            int find(int x) {\n                if (parent[x] != x) {\n                    parent[x] = find(parent[x]);\n                }\n                return parent[x];\n            }\n\n            bool unite(int x, int y) {\n                int rootX = find(x), rootY = find(y);\n                if (rootX == rootY) return false;\n                if (size[rootX] < size[rootY]) swap(rootX, rootY);\n                parent[rootY] = rootX;\n                size[rootX] += size[rootY];\n                components--;\n                return true;\n            }\n\n            bool isConnected() {\n                return components == 1;\n            }\n        };\n        \n        UnionFind alice(n), bob(n);\n        int edgesRequired = 0;\n        \n        // Process type 3 edges first\n        for (const auto& edge : edges) {\n            if (edge[0] == 3) {\n                if (alice.unite(edge[1], edge[2]) | bob.unite(edge[1], edge[2])) {\n                    edgesRequired++;\n                }\n            }\n        }\n        \n        // Process type 1 and type 2 edges\n        for (const auto& edge : edges) {\n            if (edge[0] == 1) {\n                if (alice.unite(edge[1], edge[2])) {\n                    edgesRequired++;\n                }\n            } else if (edge[0] == 2) {\n                if (bob.unite(edge[1], edge[2])) {\n                    edgesRequired++;\n                }\n            }\n        }\n        \n        // Check if both are fully connected\n        if (alice.isConnected() && bob.isConnected()) {\n            return edges.size() - edgesRequired;\n        }\n        \n        return -1;\n    }\n};\n```\n```Python []\nclass Solution(object):\n    def maxNumEdgesToRemove(self, n, edges):\n        # UnionFind class definition\n        class UnionFind:\n            def __init__(self, n):\n                self.representative = list(range(n + 1))\n                self.component_size = [1] * (n + 1)\n                self.components = n\n            \n            def find_representative(self, x):\n                if self.representative[x] == x:\n                    return x\n                self.representative[x] = self.find_representative(self.representative[x])\n                return self.representative[x]\n            \n            def perform_union(self, x, y):\n                x = self.find_representative(x)\n                y = self.find_representative(y)\n                \n                if x == y:\n                    return 0\n                \n                if self.component_size[x] > self.component_size[y]:\n                    self.component_size[x] += self.component_size[y]\n                    self.representative[y] = x\n                else:\n                    self.component_size[y] += self.component_size[x]\n                    self.representative[x] = y\n                \n                self.components -= 1\n                return 1\n            \n            def is_connected(self):\n                return self.components == 1\n        \n        # Main function logic\n        alice = UnionFind(n)\n        bob = UnionFind(n)\n        \n        edges_required = 0\n        \n        for edge in edges:\n            if edge[0] == 3:\n                edges_required += (alice.perform_union(edge[1], edge[2]) | bob.perform_union(edge[1], edge[2]))\n        \n        for edge in edges:\n            if edge[0] == 2:\n                edges_required += bob.perform_union(edge[1], edge[2])\n            elif edge[0] == 1:\n                edges_required += alice.perform_union(edge[1], edge[2])\n        \n        if alice.is_connected() and bob.is_connected():\n            return len(edges) - edges_required\n        \n        return -1\n```\n```JavaScript []\nvar maxNumEdgesToRemove = function(n, edges) {\n    // UnionFind class definition\n    class UnionFind {\n        constructor(n) {\n            this.representative = Array.from({ length: n + 1 }, (_, index) => index);\n            this.componentSize = Array.from({ length: n + 1 }, () => 1);\n            this.components = n;\n        }\n\n        findRepresentative(x) {\n            if (this.representative[x] === x) {\n                return x;\n            }\n            this.representative[x] = this.findRepresentative(this.representative[x]);\n            return this.representative[x];\n        }\n\n        performUnion(x, y) {\n            x = this.findRepresentative(x);\n            y = this.findRepresentative(y);\n\n            if (x === y) {\n                return 0;\n            }\n\n            if (this.componentSize[x] > this.componentSize[y]) {\n                this.componentSize[x] += this.componentSize[y];\n                this.representative[y] = x;\n            } else {\n                this.componentSize[y] += this.componentSize[x];\n                this.representative[x] = y;\n            }\n\n            this.components--;\n            return 1;\n        }\n\n        isConnected() {\n            return this.components === 1;\n        }\n    }\n\n    // Main function logic\n    let alice = new UnionFind(n);\n    let bob = new UnionFind(n);\n\n    let edgesRequired = 0;\n\n    for (let edge of edges) {\n        if (edge[0] === 3) {\n            edgesRequired += (alice.performUnion(edge[1], edge[2]) | bob.performUnion(edge[1], edge[2]));\n        }\n    }\n\n    for (let edge of edges) {\n        if (edge[0] === 2) {\n            edgesRequired += bob.performUnion(edge[1], edge[2]);\n        } else if (edge[0] === 1) {\n            edgesRequired += alice.performUnion(edge[1], edge[2]);\n        }\n    }\n\n    if (alice.isConnected() && bob.isConnected()) {\n        return edges.length - edgesRequired;\n    }\n\n    return -1;\n};\n```\n![upvote.png](https://assets.leetcode.com/users/images/0dd64ccd-3fe6-4704-9a53-7e54a891ef36_1719717883.987605.png)\n
['Union Find', 'Graph', 'Python', 'C++', 'Java', 'JavaScript']