# 684. Redundant Connection """ in this problem, a tree is an undirected graph that is connected and has no cycles. you are given a graph that started as a tree with 'n' nodes labeled from 1 to 'n', with one additional edge added. the added edge has two different vertices chosen from 1 to 'n', and was not an edge that already existed. the graph is represented as an array 'edges' of length 'n' where 'edges[i] = [a_i, b_i]' indicates that there is an edge between nodes 'a_i' and 'b_i' in the graph. return an edge that can removed so that the resulting graph is a tree of 'n' nodes. if there are multiple answers, return the answer that occurs last in the input. """ class Solution(object): def findRedundantConnection(self, edges): """ :type edges: List[List[int]] :rtype: List[int] """ parent = [-1] * (len(edges) + 1) rank = [0] * (len(edges) + 1) def find(x): if parent[x] == -1: return x parent[x] = find(parent[x]) return parent[x] def union_set(x, y): root_x, root_y = find(x), find(y) if root_x == root_y: return False elif rank[root_x] < rank[root_y]: parent[root_x] = root_y rank[root_y] += 1 return True else: parent[root_y] = root_x rank[root_x] += 1 return True for x, y in edges: if not union_set(x, y): return [x, y] if __name__ == "__main__": obj = Solution() print(obj.findRedundantConnection(edges=[[1, 2], [1, 3], [2, 3]])) print(obj.findRedundantConnection(edges=[[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]))