As per the editorial the final output is Acomponents+B(n-components)+A(V-n) but why did we add the term A*(V-n) as the stand alone nodes should also be counted under the components part then what is the need of it.
Secondly,i want to ask about the part B(n-components), why did we use n-components.This explaination was not clear.
Doubt regarding the problem relegious people
if temple cost is less than road cost then I return (templeCost*n)
then we proceed to the condition when cost of road is less that of temple
firstly we`ll calculate the total no of components, and store no of nodes each indepenent component has in a array / vector
so since each component requires to have ateast 1 temple we build just 1 temple [since it is costly ]in each component.
then suppose if a component has 4 nodes out of it 1 node now has a temple, so we need 3 road mantainence
so
final formula becomes when road cost is less than temple building cost
sum = no of component * cost of temple
+
for( no of component - 1 : in each component )
sum += ( no of component * cost of road repair )
u can use dfs to find no of components
its easier.
also store no of nodes in each connected component since it is used later in the calculation
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.