Участник:Polina Potapova/redundant-connection

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/redundant-connection

class Solution(object):
    def find_root(self, edge, tree):
        return edge if tree[edge] == -1 else self.find_root(tree[edge], tree)   
 
    def findRedundantConnection(self, edges):
        """
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        tree = [-1 for i in range(len(edges) + 1)]
        for edge in edges:
            root_1 = self.find_root(edge[0], tree)
            root_2 = self.find_root(edge[1], tree)
            if root_1 != root_2:
                tree[root_1] = root_2
            else:
                return edge