please explain the question… i tried solving it but i think i could not understand it properly.
I think it is about finding all the connected components…u can do it using dfs.
Consider the following testcase:
6 4
1 2
2 3
4 5
5 6
In this case the chemicals that can react with each other are:
1-2-3
and
4-5-6
In the first component (1-2-3) you can add any chemical 1st…suppose you add 1…then you add 2 and then 3…this will take the value to 4 (1*2*2). (Order does not really matter).
while adding the remaining chemicals…u can add 4 first(this will have no effect) then you can add 5 then 6 this will lead to the ans being multiplied by a factor of 4 (2 each for 5 & 6).
So the final ans will be 16.
To generalize it:
Let there be N connected components…then the ans will be…
where ln is length of nth connected component.
Hope this helps…
7 Likes
You don’t know what is the task ?
Thanks !!!
1 Like