684. 冗余连接

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

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        from collections import OrderedDict
        d = OrderedDict()
        for i in [i for j in edges for i in j]:
            d[i] = []

        for e in edges:
            d[e[0]].append(e[1])
            d[e[1]].append(e[0])

        loop = True
        while loop:
            loop = False
            for k in list(d.keys()): 
                if len(d[k]) == 1:
                    d[d[k][0]].remove(k)
                    d.pop(k)
                    loop = True
        ans = []
    #     print(d, edges)
        for e in edges[::-1]:
            if e[0] in d.keys():
                for v in d[e[0]]:
    #                 print([v,e[0]],e)
                    if [e[0],v] == e or [v,e[0]] == e:
                        return e
            if e[1] in d.keys():
                for v in d[e[1]]:
    #                 print([v,e[1]],e)
                    if [e[1],v] == e or [v,e[1]] == e :
                        return e

通过, 80 ms, 14.2 MB