number of edges in the final minimum spanning graph = n - number of connected components
Incase of a tree, (fully connected; number of connected conponents = 1)
number of edges = n-1
It is said in problem that “The fence needs to be set up such that every tree in the area is connected to the fence”, and there is no requirement that every fence must be connected to form one set (if it’s possible by tuples list). So in some cases solution could be more optimized and have lesser fence length. For example in Test#2 the expected result is 20, but we could get 15 if last fence between tree 1 and 4 with length 5 is omitted cause tree 1 is already fenced with trees 10, 2 and tree 4 is fenced with tree 9 therefore no need to take last fence 1 | 4
You should specify in the find that you’re employing path compression in the find() function and why this optimization matters.
nvm
+1 on this.
The test 2 actually can have the fence with length 11, if you also include in the priority the fact that an fence with 2 not yet connected trees has the double value (i.e. half cost). The priority gets much trickier though, and you need to recalculate it after every edge picked. This is the solution:
[
5 8 1
7 10 1
6 5 1
4 9 2
2 3 4
1 10 2
]
Also, there are a few things that are not in the description:
- The test 2 contains edges that are only possible in the directed graph:
[
…
8 5 2,
5 8 1,
5 6 2,
6 5 1
]
This makes no sense with the description on the task, and introduces a hideen layer of complexity of the task.
- The test 4 contains edges pointing to the tree itself such as
[
6 6 2,
7 7 3,
8 8 2
]
Not sure which is the idea behind that, also makes little sense with the description to me. But this can be a tricky one, if you have a test with an isolated tree that only has such an edge, so we are obligued to include these to solve the problem.
- I cannot see, how the Kruskal helps in a problem such as:
5
4
1 3 6
1 2 1
2 4 6
3 4 7
Here, the shortest solution is [{1 2 1}, {3 4 7}] with the cost of 8. However, kruskal will include other two edges while constructing the MST and in the end ignore the last one, arriving to the cost of 13. The only possible solution to this situation I see is to run backtracking with permuting all the edges,. That is too slow however, since it is O(n!) time.
- Consider this similar case to the described in the previous point:
5
4
1 3 3
1 2 2
2 4 3
3 4 5
Here, the shortest solution is [{1 3 3}, {2 4 3}] with the cost of 6, ignoring the cheapest edge. I cannot see it possible doing with the kruskal algorithm, since we may need to ignore one of the cheaper edges picked k times before.
Clarification: The sequences of numbers in my previous comment are custom test inputs. Since the platform keeps messing up with the spaces, tabulations and new line characters, I will introduce those characters manually here:
5 4 1 3 6 1 2 1 2 4 6 3 4 7 => 5\n 4\n 1 3 6\n 1 2 1\n 2 4 6\n 3 4 7\n
5 4 1 3 3 1 2 2 2 4 3 3 4 5 => 5\n 4\n 1 3 3\n 1 2 2\n 2 4 3\n 3 4 5\n
P.S: Dear authors, this problem is not well specified nor the solution is well explained. Just throwing the code does little help. I hope you elaborate it better (hope, the described cases in my previous comments help) and how they should be solved. Or find a different one, if this problem turns out to bee too complex for this topic.
Thank you
My code for Prim algo:
from typing import List
from collections import defaultdict
from heapq import *
def mst_forest(trees: int, pairs: List[List[int]]) → int:
seen=set()
adj_list = defaultdict(list)
for pair in pairs:
adj_list[pair[0]].append((pair[2],pair[1]))
adj_list[pair[1]].append((pair[2],pair[0]))
def bfs(node):
fence=0
heap=[]
heappush(heap,(0,node))
while heap:
distance,node = heappop(heap)
if node in seen:
continue
fence+=distance
for neighbor in adj_list[node]:
heappush(heap,neighbor)
seen.add(node)
return fence
total=0
for i in range(trees):
if i not in seen:
total+=bfs(i)
return total
this one can never be solved by Prim. Only Kruskal can solve it.