From DFS to Union Find
DFS\nalready_connected[x] indicates reachable nodes from x that are known so far.\nWhile we iterate through edges, for a new edge [x, y], if y is in already_con
# DFS\n`already_connected[x]` indicates reachable nodes from x that are known so far.\nWhile we iterate through edges, for a new edge `[x, y]`, if `y` is in `already_connected[x]`, the edge `[x, y]` is redundant.\n```\nclass Solution:\n    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n        self.already_connected = defaultdict(list)\n        for edge in edges:\n            self.visited = defaultdict(bool)\n            x, y = edge[0], edge[1]\n            if self.is_already_connected(x, y):\n                return edge\n            self.already_connected[x].append(y)\n            self.already_connected[y].append(x)\n            \n    def is_already_connected(self, x, y):\n        if x == y:\n            return True\n        for x_adjacent in self.already_connected[x]:\n            if not self.visited[x_adjacent]:\n                self.visited[x_adjacent] = True\n                if self.is_already_connected(x_adjacent, y):\n                    return True\n        return False\n```\n# Union Find\nAn edge will connect two nodes into one connected component.\n\nWhen we count an edge in, if two nodes have already been in the same connected component, the edge will result in a cycle. That is, the edge is redundant. \n\nWe can make use of **Disjoint Sets (Union Find)**.\n\nIf we regard a node as an element, a connected component is actually a disjoint set.\n\n>For example,\n```\nGiven edges [1, 2], [1, 3], [2, 3],\n  1\n / \\\n2 - 3\n```\n>Initially, there are 3 disjoint sets: 1, 2, 3.\nEdge [1,2] connects 1 to 2, i.e., 1 and 2 are winthin the same connected component.\nEdge [1,3] connects 1 to 3, i.e., 1 and 3 are winthin the same connected component.\nEdge [2,3] connects 2 to 3, but 2 and 3 have been winthin the same connected component already, so [2, 3] is redundant.\n\n****\n```\nclass Solution:\n    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n        parent = [-1] * (len(edges) + 1)\n        rank = [0] * (len(edges) + 1)\n\n        def find(x):\n            if parent[x] == -1:\n                return x\n            parent[x] = find(parent[x])\n            return parent[x]\n\n        def union(x, y):\n            root_x = find(x)\n            root_y = find(y)\n            if root_x == root_y:\n                return False\n            elif rank[root_x] < rank[root_y]:\n                parent[root_x] = root_y\n                rank[root_y] += 1\n                return True\n            else:\n                parent[root_y] = root_x\n                rank[root_x] += 1\n                return True\n\n        for x, y in edges:\n            if not union(x, y): \n                return [x, y]\n        \n        raise ValueError("Illegal input.")\n```\nThe **Union by Rank** and **Path Compression (in find)** can optimize the time complexity from O(n) to O(logn) (even smaller).\n\n**(\u4EBA \u2022\u0348\u1D17\u2022\u0348)** Thanks for voting!
[]