Постановка задачи:
- Удалите максимальное количество ребер, чтобы график оставался полностью проходимым
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Type 1: Can be traversed by Alice only. Type 2: Can be traversed by Bob only. Type 3: Can by traversed by both Alice and Bob.Для ребер массива, где ребра[i] знак равно [type, u, v] представляет двунаправленное ребро типа type между узлами u и v, найдите максимальное количество ребер, которое вы можете удалить, чтобы после удаления ребер граф все еще мог полностью пройти как Алиса, так и Боб. График полностью проходит Алиса и Боб, если, начиная с любого узла, они могут достичь всех остальных узлов.
Верните максимальное количество ребер, которое вы можете удалить, или верните -1, если Алиса и Боб не могут полностью пройти по графу.
Я использую алгоритм Краскала, чтобы найти MST для Алисы и Боба, и подпрограмму Explore DFS для проверки циклов и проверки подключения. Я прошел 77 из 84 тестов, но 78 раз пропустил. У меня была более быстрая версия, но она дает неправильное решение в тестовом примере 74, поэтому я отредактировал, чтобы опубликовать код ниже, время ожидания которого истекает.
class Solution:
def maxNumEdgesToRemove(self, n, edges):
'''
type 1 Alice, type 2 Bob, type 3 both
[type, u, v]
1. Use Kruskal's or Prim's so need to assign weights for Alice and Bob
:param n:
:param edges:
:return: num edges to remove
'''
# Alice 1
person = 'Alice'
a_wt_edges = self.assign_weights(person, edges)
a_mst, num_AB_Alice, num_Alice_edges, a_visited = self.kruskal(a_wt_edges, n)
# check that each vertex has at least one edge
#use dummy variables for u and v
dummy_u = 1
dummy_v = 2
connected = self.explore(a_mst, dummy_u, check_connected=True)
if not connected:
return -1
# Bob 2
person = 'Bob'
b_wt_edges = self.assign_weights(person, edges)
b_mst, num_AB_Bob, num_Bob_edges, b_visited = self.kruskal(b_wt_edges, n)
connected = self.explore(b_mst, dummy_u, check_connected=True)
if not connected:
return -1
total_graph_edges = len(edges)
#if num_AB_Alice == num_AB_Bob:
# num AB edges should be the same
combined_edges = num_AB_Alice + num_Alice_edges + num_Bob_edges
num_remove = total_graph_edges - combined_edges
return num_remove
def kruskal(self, wt_edges, n):
'''
run Kruskal, add lightest edge if it does not make cycle
keep track of visited, run explore once all v's visited
if explore returns True, break and return since MST is connected
todo: exit when mst is connected
:param wt_edges:
:return: mst, num edges AB
'''
# 0 indexing leave zero with no edges
# check connectivity here not call explore again
visited = [-1 for x in range(n+1)]
visited[0] = 1
mst = {i:[] for i in range(1, n+1)}
num_AB = 0
num_persons_edges = 0
for i in range(len(wt_edges)):
low_edge = wt_edges.pop(0)
curr_wt, u, v = low_edge[0], low_edge[1], low_edge[2]
# for speedup
if i == 0: #or i == 1:
makes_cycle = False
else:
makes_cycle = self.explore(mst, u, v)
if makes_cycle:
continue
# no cycle so add edge
mst[u].append(v)
#undirected so add other direction
mst[v].append(u)
visited[u] = 1
visited[v] = 1
if curr_wt is 1:
num_AB += 1
else:
num_persons_edges +=1
# check if MST is connected if all v's are at least visited
# still could be missing edges crossing the cut from S to S'
# if connected, break
if -1 not in visited:
if self.explore(mst, 1, check_connected=True):
break
return mst, num_AB, num_persons_edges, visited
def explore(self, graph, u, v=None, check_connected=False):
'''
if explore reaches v from u, the edge being considered would create a cycle
:param mst:
:param u:
:param v:
:param n:
:return:
'''
# 0 indexing
visited = [0 for x in range(0, len(graph)+1)]
stack = [u]
while stack:
start = stack.pop()
visited[start] = 1
dst_vertices = graph[start]
for vert in dst_vertices:
if not visited[vert]:
stack.append(vert)
if check_connected:
visited[0] = 1
if 0 in visited: #return False if there are any unvisited vertices
return False
return True #'connected'
else:
if visited[v]:
return True # makes cycle
return False
def assign_weights(self, person, edges):
'''
:param person:
:param edges:
:return: list of lists of [wt, u, v]
'''
#adj_matrix
#wt_edges = [[0 for x in range(len(edges[0]))] for y in range(len(edges))]
wt_edges = []
for i in range(len(edges)):
curr_edge = edges[i]
edge_type = curr_edge[0]
u = curr_edge[1]
v = curr_edge[2]
if edge_type == 3: #both A and B
wt_edges.append([1, u, v])
elif edge_type is 1:
if person is 'Alice':
wt_edges.append([2,u,v])
else: # Bob so toss this edge
continue
elif edge_type is 2:
if person is 'Bob':
wt_edges.append([2,u,v])
else: #Alice so toss this edge
continue
#wt_edges_sorted = self.sort_edges(wt_edges)
wt_edges_sorted = sorted(wt_edges, key=lambda x: x[0])
return wt_edges_sorted
Полный код с контрольным примером, время ожидания которого истекло, находится здесь: https://github.com/nyck33/coding_practice/blob/master/removeMaxEdges.py
Примечание: в моей попытке оптимизировать (предыдущий код, который у меня был здесь) я не назначал веса и сортировку ребер, как здесь. Скорее, я использовал составление списков, чтобы составить 3 отдельных списка ребер, которые были только Алисой, только Бобом или обоими.