Python | Easy | Graph |  Remove Max Number of Edges to Keep Graph Fully Traversable
\nsee the Successfully Accepted Submission\nPython\nclass Solution:\n    def maxNumEdgesToRemove(self, n, edges):\n        def find(x, parent):\n            if 
\n[see the Successfully Accepted Submission](https://leetcode.com/submissions/detail/1071110896/)\n```Python\nclass Solution:\n    def maxNumEdgesToRemove(self, n, edges):\n        def find(x, parent):\n            if parent[x] != x:\n                parent[x] = find(parent[x], parent)\n            return parent[x]\n\n        def union(x, y, parent):\n            parent[find(x, parent)] = find(y, parent)\n\n        dsu1 = list(range(n + 1))\n        dsu2 = list(range(n + 1))\n        count = 0\n        edges.sort(key=lambda x: x[0], reverse=True)\n\n        for edge in edges:\n            if edge[0] == 3:\n                if find(edge[1], dsu1) == find(edge[2], dsu1) and find(edge[1], dsu2) == find(edge[2], dsu2):\n                    count += 1\n                    continue\n\n                union(edge[1], edge[2], dsu1)\n                union(edge[1], edge[2], dsu2)\n            elif edge[0] == 1:\n                if find(edge[1], dsu1) == find(edge[2], dsu1):\n                    count += 1\n\n                union(edge[1], edge[2], dsu1)\n            else:\n                if find(edge[1], dsu2) == find(edge[2], dsu2):\n                    count += 1\n\n                union(edge[1], edge[2], dsu2)\n\n        for i in range(1, n + 1):\n            find(i, dsu1)\n            find(i, dsu2)\n\n        for i in range(2, n + 1):\n            if dsu1[i] != dsu1[1] or dsu2[i] != dsu2[1]:\n                return -1\n\n        return count\n\n```\n\n**Intuituin**\n \n```\n    def maxNumEdgesToRemove(self, n, edges):\n```\nDefine a helper function to find the parent of a set using path compression.\n```\n        def find(x, parent):\n            if parent[x] != x:\n                parent[x] = find(parent[x], parent)\n            return parent[x]\n```\n\n\nDefine a helper function to union two sets.\n```\n        def union(x, y, parent):\n            parent[find(x, parent)] = find(y, parent)\n```\n\nCreate two disjoint set arrays dsu1 and dsu2 for Alice and Bob.\n```\n        dsu1 = list(range(n + 1))\n        dsu2 = list(range(n + 1))\n        count = 0  # Initialize a counter for the removed edges.\n```\n\n\nSort the edges in descending order so that we prioritize removing type-3 edges.\n```\n        edges.sort(key=lambda x: x[0], reverse=True)\n\n        for edge in edges:\n            if edge[0] == 3:\n```\n\n Type-3 edge, check if the nodes are already in the same set for both Alice and Bob.\n ```\n                if find(edge[1], dsu1) == find(edge[2], dsu1) and find(edge[1], dsu2) == find(edge[2], dsu2):\n```\n\n```\n                    count += 1  # Increment the count of removed edges.\n                    continue\n```\n\nUnion the nodes in both dsu1 and dsu2.\n```\n                union(edge[1], edge[2], dsu1)\n                union(edge[1], edge[2], dsu2)\n            elif edge[0] == 1:\n```\n\nType-1 edge, check if the nodes are already in the same set for Alice.\n```\n                if find(edge[1], dsu1) == find(edge[2], dsu1):\n```\n\n Increment the count of removed edges.\n```\n                    count += 1 \n```\n\nUnion the nodes in dsu1.\n```\n                union(edge[1], edge[2], dsu1)\n            else:\n```\n\nType-2 edge, check if the nodes are already in the same set for Bob.\n```\n                if find(edge[1], dsu2) == find(edge[2], dsu2):\n                    count += 1  # Increment the count of removed edges.\n```\n\nUnion the nodes in dsu2.\n```\n                union(edge[1], edge[2], dsu2)\n```\n\nEnsure that all nodes in dsu1 and dsu2 have the same parent (representing a single set).\n```\n        for i in range(1, n + 1):\n            find(i, dsu1)\n            find(i, dsu2)\n```\n\n\nCheck if all nodes in both dsu1 and dsu2 belong to the same set.\n```\n        for i in range(2, n + 1):\n            if dsu1[i] != dsu1[1] or dsu2[i] != dsu2[1]:\n\t\t\t\n```\n\nIf not, it\'s not possible to remove all edges.\n```\n                return -1 \n```\n\nReturn the count of removed edges, which represents the maximum possible.\n```\n        return count \n```\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)\n\n\n
['Graph', 'Python']