684. 冗余连接

image.png

class Solution:
    def findRedundantConnection(self, edges):
        """
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        import copy

        dict={}
        def insert_dict(s,d):
            if dict.__contains__(s):
                dict[s][d]=1
            else:
                dict[s]={d:1}
        for edge in edges:
            insert_dict(edge[0],edge[1])
            insert_dict(edge[1],edge[0])

        def func(all_node):
            bool_dict={i:False for  i in all_node}
            s=all_node[0]
            def tran(node):
                if node==None:
                    return

                if bool_dict[node]==True:
                    return
                else:
                    bool_dict[node]=True
                    sons=dict[node].keys()
                    for i in sons:
                        tran(i)
            tran(s)
            if False not in bool_dict.values():
                return True
            else:
                return False
        o_nodes=list(dict.keys())
        o_dict=copy.deepcopy(dict)
        for del_e in edges[::-1]:
            dict=copy.deepcopy(o_dict)
            del dict[del_e[0]][del_e[1]]
            del dict[del_e[1]][del_e[0]]
            if  func(o_nodes):
                return del_e