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
