https://www.hackerrank.com/challenges/torque-and-development/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=graphs
W tym zadaniu musze okreslic minimalny koszt budowy bibliotek dostepnych dla kazdego obywatela. Aby biblioteka spelniala takie wymagania, musi byc dostepna od kazdego wierzcholka grafu. Moj algorytm: usuń wszystkie cykle z grafu, po czym zaplac za wszystkie pozostale krawedzie (drogi). Nastepnie zaplac za jedną biblioteka dla kazdego "komponentu grafu", tzn musze wykryc na ile silnie połączonych podgrafów dzieli sie dany graf. Zapisane to jest tak, roadsAndLibraries
to funkcja wyjsciowa (nie wiem jak operowac na strukturze tablicy 2d, wiec zamieniam ją na słownik wierzchołków)
def changeToDic(arr):
dic={}
for a in arr:
if a[0] not in dic:
dic[a[0]]=[a[1]]
else: dic[a[0]].append(a[1])
if a[1] not in dic:
dic[a[1]]=[a[0]]
else: dic[a[1]].append(a[0])
return dic
def changeToArr(dic):
lst=[]
for k in dic.keys():
for v in dic[k]:
lst.append([k,v])
return lst
def DFS(t1,toDel=[]):
parent={}
c=0
for neigh in t1:
if neigh not in parent:
parent[neigh]=None
c+=1
DFSVisit(t1,neigh,parent,toDel)
return [toDel,c]
def DFSVisit(adj,s,parent,td):
for v in adj[s]:
if v not in parent:
parent[v]=s
print(s,"->",v)
DFSVisit(adj,v,parent,td)
else:
print("There is a cycle {} -> {}".format(s,v))
td.append([s,v])
def deleteCycles(arr,dic):
for a in arr:
dic[a[0]].remove(a[1])
return dic
def roadsAndLibraries(n,c_lib,c_road,cities):
dic=changeToDic(cities)
if c_lib<c_road:
return c_lib*len(dic)
else:
td=DFS(dic)
dic=deleteCycles(td[0],dic)
arrDic=changeToArr(dic)
return (roadCost*len(arrDic))+(libCost*td[1])
Dostaje złą odpowiedź nawet dla trywialnego przykładu:
[[1, 2], [1, 3], [1, 4]] Koszt biblioteki: 6 Koszt drogi 1
Ten graf nie ma cykli więc wystarczy zapłacić za 3 drogi i za jedną biblioteke do której każde miasto będzie miało dostęp. Wychodzi 9 jak byk a w "Expected Output": 15. Dlaczego tak?