Участник:Turk0v/Redundant Connection II

Материал из DISCOPAL
Перейти к: навигация, поиск
 
class Solution:
    def find(self,p, c):
        while c != p[c]:
            p[c] = p[p[c]]
            c = p[c]
        return c
 
    def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:
        res1 = None
        res2 = None
        p = [i for i in range(len(edges) + 2)]
        for e in edges:
            if p[e[1]] == e[1]:
                p[e[1]] = e[0]
            else:
                res1 = [p[e[1]],e[1]]
                res2 = [e[0], e[1]]
                e[1] = 0
        p = [i for i in range(len(edges) + 2)]
        for e in edges:
            if e[1] == 0:
                continue
            if self.find(p, e[0]) == e[1]:
                return res1 if res1 else e
            p[e[1]] = e[0]
        return res2