We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
It took me a while to understand what @zac_c_petit was saying, since I didn't know how to do it and DFS for every node sounded foolish.
The idea is:
sort the edges in descending order.
For every edge pair:
Join if at most one component/group/set has a machine (you can figure this out in O(1) amortized time by augmenting disjoint set (same cost as for find))
else you need to destroy that road (add it to your total cost)
Here's the code in Python (assuming we have already implemented augmented Disjoint Set)
# Complete the minTime function below.defminTime(roads,machines):cities_set=DisjointSet()cost_to_separate_two_machines=0formachineinmachines:cities_set.make_set(machine,is_machine=True)## sort edges. Greatest firstsorted_edges=sorted(roads,key=lambdaroad:road[2],reverse=True)fornode_a,node_b,costinsorted_edges:ifcities_set.has_machine_in(node_a)andcities_set.has_machine_in(node_b):cost_to_separate_two_machines+=costelse:cities_set.union(node_a,node_b)returncost_to_separate_two_machines
Matrix
You are viewing a single comment's thread. Return to all comments →
It took me a while to understand what @zac_c_petit was saying, since I didn't know how to do it and DFS for every node sounded foolish.
The idea is:
Here's the code in Python (assuming we have already implemented augmented Disjoint Set)