DZY loves chemistry (codeforces contest #254 div 2)

http://codeforces.com/contest/445/problem/B

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…

alt text

where ln is length of nth connected component.

Hope this helps…:slight_smile:

5 Likes

You don’t know what is the task ?

Thanks !!!

1 Like