節点を頂点、電気抵抗を辺とみなしたグラフを考えます。

選べる辺の条件として、取り除いた後のグラフが二部グラフである必要があります。また、取り除いた辺が結ぶ頂点を \(a,b\) とすると、\(a,b\) が連結なら、\(a,b\) の電位が等しいか異なるかが分かります。取り除いた後のグラフでの \(a,b\) のパス長が奇数だと、\(a,b\) の電位は異なってしまいます。つまり、取り除く辺は元のグラフで偶閉路の辺であってはいけません。

逆に、この2つの条件を満たす辺、つまり

1. その辺を取り除いた後のグラフが二部グラフであり、
2. その辺は元のグラフで偶閉路に含まれない

ような辺は取り除いても問題ありません。（そのような辺の両端点の電位を定め、そこから隣接する頂点の電位を順に決めれば良いです。電位が設定できない時、仮定1. と2. に矛盾することが分かります。）

以後、この2つの条件を満たす辺を数えます。

まず、元のグラフ \(G\) が二部グラフの場合、いずれの辺も取り除いた後は二部グラフです。よって、\(G\) 上で偶閉路上にない辺を数えればよく、これは各連結成分における橋の総数に相当します。橋は \(O(N+M)\) で列挙できます。

元のグラフ \(G\) が二部グラフでない場合を考えます。この場合、奇閉路 \(C\) を一つ見つけると、選べる辺は \(C\) 上に限られます。そこで、\(C\) の全ての辺を取り除いたグラフ \(G\backslash C\) を考えます。\(G\backslash C\) が二部グラフでない場合、 \(G\) から \(C\) 内のいずれの1辺を取り除いても二部グラフにはなりません。よって、答えは \(0\) です。

\(G\backslash C\) が二部グラフの場合、残ったグラフの各連結成分について探索を行います。ある頂点 \(u\) から連結成分の電位をDFSなどで決定することで、サイクル上のいくつかの頂点 \(v\) に対して「\(u\) と同じ電位か」が分かります。この情報と、\(C\) 上での \(u,v\) の距離を比べれば、\(C\) においてどの区間に取り除くべき辺があるかが分かります。この情報を全ての連結成分について取りまとめて、全ての区間に含まれているような辺の個数を数えれば良いです。この情報の個数は \(C\) のサイクル長以下になります。

\(C\) において取り除くべき辺が存在しうる区間がたくさん与えられた時に、その全ての区間に含まれるような辺を数えるのは、例えば区間の外側に1を加算し、最後に合計が0になっている場所の個数を数えると考えれば、累積和によって実現できます。