truck driver(改)

この問題は、$N$頂点$M$辺のグラフとして考えると、

運べない可能性があるのは閉路の中で無限ループするときか、連結していないときが考えられます。

よって、無限ループしないためには閉路の橋を一つずつ壊すことにより実現できます。

ただし、$1～N$まですべての頂点がつながれている閉路、いわゆるハミルトン閉路がある際は、壊すべき道は一つ減ります。 (ハミルトン閉路がある際はその部分だけ残して残りを壊せばよいため)

これは、bitDFSで高速化することにより$O(2^NN)$で求めることができます。