Grafy - usuwanie cykli i liczenie komponentow. Co robie zle

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?

Skąd Wziąłeś to 15, przecież to jest 9.
Jeszcze, koszt "wybudowania" biblioteki może byc mniejszy niż nowych dróg, to też trzeba uwzględnić, więc nie można automatycznie "odbudowywać".

lion137 napisał(a):

Skąd Wziąłeś to 15, przecież to jest 9.
Jeszcze, koszt "wybudowania" biblioteki może byc mniejszy niż nowych dróg, to też trzeba uwzględnić, więc nie można automatycznie "odbudowywać".

https://imgur.com/1DTk2ju
u Ciebie przechodzi ten test case?
jw uwzgledniam, ze koszt biblioteki moze byc mniejszy wtedy buduje biblioteke w kazdym miescie, nie buduje drog

nie tak, dla tego przypadku jest:

1
4 3 6 1
1 2
1 3
1 4

cztery miasta, trzy drogi.

lion137 napisał(a):

nie tak, dla tego przypadku jest:

1
4 3 6 1
1 2
1 3
1 4

cztery miasta, trzy drogi.

czyli tam powinno byc

 [[4,3],[1,2],[1,3],[1,4]]

?
"cztery miasta trzy drogi"
No dokladnie. 2 3 4 są połączone z 1, wystarczy 1 biblioteka do obsłużenia ich wszystkich, tylko trzeba wybudowac wszystkie trzy drogi. Wychodzi 9

Wychodzi 9 i jest 9, pierwsza linijka wejścia: 1, druga: 4 3 6 1, potem m = 3 linijek:
1 2
1 3
1 4

nie wiem co sie stało

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the roadsAndLibraries function below.
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):
    print(cities, c_lib,c_road)
    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 (c_road*len(arrDic))+(c_lib*td[1])
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    q = int(input())

    for q_itr in range(q):
        nmC_libC_road = input().split()

        n = int(nmC_libC_road[0])

        m = int(nmC_libC_road[1])

        c_lib = int(nmC_libC_road[2])

        c_road = int(nmC_libC_road[3])

        cities = []

        for _ in range(m):
            cities.append(list(map(int, input().rstrip().split())))

        result = roadsAndLibraries(n, c_lib, c_road, cities)

        fptr.write(str(result) + '\n')

    fptr.close()

Prostsze rozwiązanie:

1. iterujemy po wszystkich miastach, dla każdego nieodwiedzonego miasta:
   a) mamy nieodwiedzone miasto => czyli trafiliśmy na nowy podgraf : cities_with_library++
   b) zapuszczasz DFS z tego miasta, oznaczasz wszystkie odwiedzone wierzchołki, zliczając przy okazji liczbę dróg roads++
2. wypisujesz wynik Math.Min(roads * road_cost + cities_with_library* library_cost, n * library_cost);

Nie wyważaj otwartych drzwi, Algorytm Lawasza-Jonsona-Hwatala czyli minimalne pokrycie.