Image Explanation🏆- [Easiest & Complete Intuition] - C++/Java/Python
Video Solution (Aryan Mittal) - Link in LeetCode Profile\nRemove Max Number of Edges to Keep Graph Fully Traversable by Aryan Mittal\n\n\n\n# Approach & Intutio
# Video Solution (`Aryan Mittal`) - Link in LeetCode Profile\n`Remove Max Number of Edges to Keep Graph Fully Traversable` by `Aryan Mittal`\n![lc.png](https://assets.leetcode.com/users/images/a5f3580b-5ef1-44c7-b9d6-c194c4588dc2_1682819037.469955.png)\n\n\n# Approach & Intution\n![image.png](https://assets.leetcode.com/users/images/021bc978-11d2-4a11-9de1-dee362d67309_1682818399.3212633.png)\n![image.png](https://assets.leetcode.com/users/images/a1e85df9-7d16-4fb4-a04d-baa9dfa4087e_1682818408.9161522.png)\n![image.png](https://assets.leetcode.com/users/images/970b6e4f-4ab1-4762-b1aa-9df606097b65_1682818422.780898.png)\n![image.png](https://assets.leetcode.com/users/images/1e4e315a-8954-4ae4-94f5-65f63becd770_1682818440.0835755.png)\n![image.png](https://assets.leetcode.com/users/images/0529a674-bd29-41ff-9417-337636abf9fa_1682818452.1050658.png)\n![image.png](https://assets.leetcode.com/users/images/9a51dcc0-d1f4-44bc-a2d8-d5fca25e04e1_1682818471.9856927.png)\n![image.png](https://assets.leetcode.com/users/images/bd099e1c-b023-4a07-9955-5b683ddb5ed3_1682818479.443172.png)\n![image.png](https://assets.leetcode.com/users/images/1aac4488-e4c7-466e-8570-ffeaba83fefe_1682818492.1441891.png)\n![image.png](https://assets.leetcode.com/users/images/387e113b-a8d1-41a3-aeea-f845acf3ec12_1682818499.3856347.png)\n![image.png](https://assets.leetcode.com/users/images/23b8e642-ba76-44b2-b854-7c89fcca7113_1682818510.7526262.png)\n![image.png](https://assets.leetcode.com/users/images/e9843723-ce97-4b6c-8cbe-dfeafb99756c_1682818525.044252.png)\n![image.png](https://assets.leetcode.com/users/images/fca0cfa7-da66-460f-a55c-ab17cbff4cfc_1682818533.878107.png)\n![image.png](https://assets.leetcode.com/users/images/5cb07d8d-606c-480f-b8b0-bb7c0ddb7950_1682818543.163168.png)\n![image.png](https://assets.leetcode.com/users/images/c7cb773a-3525-4e4e-a7d6-cfe8f0945b4c_1682818550.6547136.png)\n\n\n# Code\n```C++ []\nclass DSU {\npublic:\n    vector<int> parent, rank;\n    DSU(int n){\n        parent.resize(n, 0);\n        rank.resize(n, 0);\n        \n        for(int i=0;i<n;i++) parent[i] = i;\n    }\n    \n    int Find(int x){\n        return parent[x] = parent[x] == x ? x : Find(parent[x]);\n    }\n    \n    bool Union(int x, int y){\n        int xset = Find(x), yset = Find(y);\n        if(xset != yset){\n            rank[xset] < rank[yset] ? parent[xset] = yset : parent[yset] = xset;\n            rank[xset] += rank[xset] == rank[yset];\n            return true;\n        }\n        return false;\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        DSU dsu_alice(n+1);\n        DSU dsu_bob(n+1);\n\n        int removed_edge = 0, alice_edges=0, bob_edges=0;\n        for(auto edge : edges){\n            if(edge[0] == 3){\n                if(dsu_alice.Union(edge[1], edge[2])){ // Both Alice & Bob\n                    dsu_bob.Union(edge[1], edge[2]);\n                    alice_edges++;\n                    bob_edges++;\n                }else{\n                    removed_edge++;\n                }\n            }else if(edge[0] == 2){ //Only Bob\n                if(dsu_bob.Union(edge[1], edge[2])){\n                    bob_edges++;\n                }else{\n                    removed_edge++;\n                }\n            }else{ // Only Alice\n                if(dsu_alice.Union(edge[1], edge[2])){\n                    alice_edges++;\n                }else{\n                    removed_edge++;\n                }\n            }\n        }\n\n        return (bob_edges == n - 1 && alice_edges == n - 1) ? removed_edge : -1;\n    }\n};\n```\n```Java []\nclass DSU {\n    int[] parent;\n    int[] rank;\n    \n    public DSU(int n) {\n        parent = new int[n];\n        rank = new int[n];\n        for (int i = 0; i < n; i++) {\n            parent[i] = i;\n        }\n    }\n    \n    public int find(int x) {\n        if (parent[x] != x) {\n            parent[x] = find(parent[x]);\n        }\n        return parent[x];\n    }\n    \n    public boolean union(int x, int y) {\n        int xset = find(x), yset = find(y);\n        if (xset != yset) {\n            if (rank[xset] < rank[yset]) {\n                parent[xset] = yset;\n            } else if (rank[xset] > rank[yset]) {\n                parent[yset] = xset;\n            } else {\n                parent[xset] = yset;\n                rank[yset]++;\n            }\n            return true;\n        }\n        return false;\n    }\n}\n\nclass Solution {\n    public int maxNumEdgesToRemove(int n, int[][] edges) {\n        Arrays.sort(edges, (a, b) -> Integer.compare(b[0], a[0]));\n        \n        DSU dsu_alice = new DSU(n+1);\n        DSU dsu_bob = new DSU(n+1);\n        \n        int removed_edge = 0, alice_edges = 0, bob_edges = 0;\n        for (int[] edge : edges) {\n            if (edge[0] == 3) {\n                if (dsu_alice.union(edge[1], edge[2])) {\n                    dsu_bob.union(edge[1], edge[2]);\n                    alice_edges++;\n                    bob_edges++;\n                } else {\n                    removed_edge++;\n                }\n            } else if (edge[0] == 2) {\n                if (dsu_bob.union(edge[1], edge[2])) {\n                    bob_edges++;\n                } else {\n                    removed_edge++;\n                }\n            } else {\n                if (dsu_alice.union(edge[1], edge[2])) {\n                    alice_edges++;\n                } else {\n                    removed_edge++;\n                }\n            }\n        }\n        \n        return (bob_edges == n - 1 && alice_edges == n - 1) ? removed_edge : -1;\n    }\n}\n```\n```Python []\nclass DSU:\n    def __init__(self, n):\n        self.parent = [i for i in range(n)]\n        self.rank = [0] * n\n    \n    def find(self, x):\n        if self.parent[x] != x:\n            self.parent[x] = self.find(self.parent[x])\n        return self.parent[x]\n    \n    def union(self, x, y):\n        xset, yset = self.find(x), self.find(y)\n        if xset != yset:\n            if self.rank[xset] < self.rank[yset]:\n                self.parent[xset] = yset\n            elif self.rank[xset] > self.rank[yset]:\n                self.parent[yset] = xset\n            else:\n                self.parent[xset] = yset\n                self.rank[yset] += 1\n            return True\n        return False\n\nclass Solution:\n    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n        edges.sort(reverse=True)\n        dsu_alice = DSU(n+1)\n        dsu_bob = DSU(n+1)\n        removed_edge = 0\n        alice_edges, bob_edges = 0, 0\n        for edge in edges:\n            if edge[0] == 3:\n                if dsu_alice.union(edge[1], edge[2]):\n                    dsu_bob.union(edge[1], edge[2])\n                    alice_edges += 1\n                    bob_edges += 1\n                else:\n                    removed_edge += 1\n            elif edge[0] == 2:\n                if dsu_bob.union(edge[1], edge[2]):\n                    bob_edges += 1\n                else:\n                    removed_edge += 1\n            else:\n                if dsu_alice.union(edge[1], edge[2]):\n                    alice_edges += 1\n                else:\n                    removed_edge += 1\n        return removed_edge if bob_edges == n - 1 == alice_edges else -1\n```
['Union Find', 'Graph', 'C++', 'Java', 'Python3']