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

please explain the question… i tried solving it but i think i could not understand it properly.

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

please explain the question… i tried solving it but i think i could not understand it properly.

You don’t know what is the task ?

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…

5 Likes

Thanks !!!

1 Like