Minimum Spanning Tree | Forests
The Umbristan Department of Forestry(UDF) is tackling a rather difficult problem and the Umbristan government has detached you one of its best workers to go resolve the issue. When you arrive you are quickly briefed on the problem at hand. Inside the Umbristan National Park there exists an area that has been closed off as fencing needs to be erected in the area. Your job is to split the area into different regions by connecting fences to the trees. The department has set up some rules for the fences
The department has counted the number of trees in the area as well as determined all possible tree pairs where a fence can be built between the pair.
The fences needs to be set up such that every tree in the area is connected to a fence.
The fences should be connected to one another unless a connecting fence is unable to be built (you should be able to visit all the trees by walking along the fence, except when the it's impossible using the list provided by the department)
The department is on a very strict operating budget, so you need to minimize the metres of fencing required.
Can you help them figure out the smallest amount of fencing required?
It is possible that not all the nodes will be connected to one another depending on the tree pairs.
Input will consist of
trees the number of trees in the area labelled from
n as well as pairs, a list consisting of the tuple
[a, b, d] which denotes that a fence can be built between the trees
b that will be
d metres in length.
1 <= trees <= 10^5
trees = 5, pairs = [[1, 2, 1], [2, 4, 2], [3, 5, 3], [4, 4, 4]]
We can erect fencing between trees for the following pairs,
With this every tree is connected by a fence and we have used
6 metres of fencing.