Solutions:
Build a graph data structure, list1 keep one char's neighbor information. list2 keeps each edge that is two chars.
for loop list2, firstly disconnect each edge neighborhood relationship, the do a DFS to look if can arrive from A to B, if it is true, the edge is a bridge that can bomb it, then place it to the result list. After that, connect the edge.
3. Print the result list.
def ishaltAB(list1):
stacklist = []
stacklist.append(0)
visited = []
for i in range(26):
visited.append(0)
visited[0] = 1
while len(stacklist) > 0:
n = stacklist.pop()
for i in range(26):
if list1[n][i] == 1 and visited[i] == 0:
if i == 1:
return False
else:
visited[i] = 1
stacklist.append(i)
return True
list1 = []
list2 = []
for i in range(26):
cur = []
for j in range(26):
cur.append(0)
list1.append(cur)
while True:
curs = input()
if curs == '**':
break
list2.append(curs)
n1 = ord(curs[0]) - ord('A')
n2 = ord(curs[1]) - ord('A')
list1[n1][n2] = 1
list1[n2][n1] = 1
result = []
for x in list2:
n1 = ord(x[0]) - ord('A')
n2 = ord(x[1]) - ord('A')
list1[n1][n2] = 0
list1[n2][n1] = 0
if ishaltAB(list1):
result.append(x)
list1[n1][n2] = 1
list1[n2][n1] = 1
for x in result:
print(x)
print("There are "+str(len(result))+" disconnecting roads.")
Komentarze