Religious people question

#1

required changes?

#2

@Vibhuti0206
First of all fix the compilation errors in your code. After that your code fails for several testcases like
1
4 2 2 1
1 3
3 2
Expected Output :
6 (two temples and two road, 4 is isolated)

Here’s some hint as to how to approach the problem :
Count the number of disjoint components (subgraphs which are not connected to each other) and store them in a variable , say ‘components’
Each component must have a single Temple
So cost of temple in each component is acomponents
Further there are (x-1) roads required in each component where x is no of vertices in that component
Sum of roads in all components = (n - components) , n is no of nodes in adjacency list
Multiply that with b , cost to repair each road
Cost so far , cost = acomponent + b*(n-component)

But there are some vertices that do not form any edges
Some vertices which stand alone and each of these vertices must have a temple of its own
Since they do not form any edge , there count is not included in the adjacency list
No of such nodes is (V - n) …where V is total no of nodes and n is no of nodes that form an edge and are part of previously counted components
Since each of these nodes must have a temple
Total cost = acomponent + b(n-component) + a*(V-n)

Do not forget to consider the base case when a<=b

#3
#4

how to remove the compilation errors and modifications requied?

#5

@Vibhuti0206
Your dfsHelper function accepts argument map of type unordered_map<int,bool> while you are providing it with a map of type unordered_map<long int,bool> in cost () . Stick to either int or long int throughout your code. Infact my recommendation would be to forget both and use long long int throughout the code.

Also another error is due to a spelling mistake. You have written ‘end’ instead of ‘endl’ in a cout statement.

Initialise ans from 0 and count from 1.
And again , change all instances of variables to long long int.

#6

https://ide.codingblocks.com/s/167249,i have made the required changes…but the code is not getting submitted i have tried multiple times…is there still any error or modifications required in the code

#7

@Vibhuti0206
You should reinitialise Graph G object for every new testcase or your subsequent graphs will continue to hold old graph values and produce incorrect results.

Also initialise component=0 instead of 1 before the loop since you have 0 components at the beginning.

#8

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.