[Pyhon] DSU solution, explained
Actually, what we need to do in this problem is to find loop. We can do it, using dfs or we can use Union Find idea. Let us add edges one by one and when we see
Actually, what we need to do in this problem is to find loop. We can do it, using dfs or we can use Union Find idea. Let us add edges one by one and when we see that we have a loop, that is two ends of our connection were already in the same component, we return it immedietly. Note, that because nodes enumerated from `1`, not `0`, we need to deal with this as well.\n\n#### Complexity\nIn this problem we have tree with one edge added, so there will be both `n` nodes and edges. So, if we assume that operations for our union find structure can be done in `O(1)`, total complexity will be `O(n)`. (In fact in my code I use dsu without ranks and with paths compression for simplicity, but due to small tests it works almost the same, in theory it is `O(log n)` complexity). Space complexity is `O(n)` as well.\n\n\n```python\nclass DSU:\n    def __init__(self, N):\n        self.p = list(range(N))\n\n    def find(self, x):\n        if self.p[x] != x:\n            self.p[x] = self.find(self.p[x])\n        return self.p[x]\n\n    def union(self, x, y):\n        xr = self.find(x)\n        yr = self.find(y)\n        self.p[xr] = yr\n\nclass Solution:\n    def findRedundantConnection(self, edges):\n        N = len(set(chain(*edges)))\n        dsu = DSU(N)\n        for i, j in edges:\n            if dsu.find(i-1) == dsu.find(j-1):\n                return([i,j])\n            else:\n                dsu.union(i-1,j-1)\n```\n\nIf you have any question, feel free to ask. If you like the explanations, please **Upvote!**
['Union Find']