|
|
back to boardWhy the answer is Number_of_Compartments-1 who can prove it Re: Why the answer is Number_of_Compartments-1 Posted by viknick 21 Feb 2015 22:05 if the amount of baffles that should be opened is equal to N - 2, it will be not enough, because graph will be not connected, and that's why not all cockcroaches will reach the floodgate. But you can build the spanning tree of this graph. It has exactly N - 1 edges, and graph will be connected and now all cockroaches will reach the floodgate. |
|
|