Python | Disjoint Set Union
see the Successfully Accepted Submission\n\n# Code\n\nclass Solution:\n    def maxNumEdgesToRemove(self, n, edges):\n        def find(x, parent):\n            i
[see the Successfully Accepted Submission](https://leetcode.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/submissions/1304542402/?envType=daily-question&envId=2024-06-30)\n\n# Code\n```\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![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']