条件を満たすウォークの有無は、実は以下のようなウォークの有無と一致します。

• 始点と終点が同じで、各辺を \(1\) 回以上用いる
• 辺のラベルが (, ) であるものが（複数回使用した場合はその分カウントするとして）同数ずつ用いられている

これは (, ) が同数含まれている文字列は（prefixの開き括弧の数）\(-\) （prefixの閉じ括弧の数）が最小になる部分が末尾になるように cyclic-shift することで正しい括弧列になる（例えば )())(( であれば \(4\) 回 cyclic-shift して (()()) にすると正しい括弧列になっています）ことから、上記のようなウォークが見つかった場合は始点を適切に選びなおすことで元の条件を満たすウォークになるからです。以下、上記のようなウォークの有無を判定することを考えます。

ウォークはいくつかの閉路を組み合わせたものと考えられます（閉路を組み合わせたものがウォークになることはオイラー閉路の存在条件を考えればわかります）。このため、条件を満たすウォークの構成方法としては

• 各辺について、辺を用いるような閉路を \(1\) つとって、それらを組み合わせてウォークをつくる。このような閉路がとれることはグラフの強連結性から保証される。
• (,) の数をそろえるため、最初に作ったウォークを複数回周回するようにしたり、あたらしい閉路を追加して調整する

といったものが考えられます。例えば最初に ( の数が ) の数より \(8\) 多い閉路 \(C_1\) ができ、 ( の数が ) の数より \(3\) 小さい閉路 \(C_2\) が取れる場合は、 \(C_1\) を \(3\) 周するウォークと \(C_2\) を \(8\) 周するウォークを取ってオイラー閉路を取り直すことで条件を満たすウォークが作れます。

上記のように閉路を何倍かにすることができるので一見ほとんどの場合条件を満たすウォークが取れるように思えますが、重要なこととして閉路を負の回数周回するということができません。このため、閉路については (,) のどちらが多いかというのが重要です。

以下では ( のほうが多い閉路と ) のほうが多い閉路の存在によって場合分けして考えます。

1. いずれの閉路も存在する場合

この場合は上記のような構築方法において、最初につくったウォークにおいて (,) のどちらが多いかに基づいて閉路を選んで調節することができます。

2. いずれの閉路も存在しない場合

これはどのような閉路も (, ) の数が等しいということを意味します。よって最初につくったウォークにおいても (, ) の数が等しいことが言えるので、条件を満たすウォークが存在することが分かります。

3. 片方の閉路が存在する場合

この場合、実は条件を満たすウォークが存在しません。背理法により示します。 ( の数が多い閉路が存在するとして一般性を失いません。

条件を満たすウォークが存在すると仮定し、これを \(C_1\) とします。また、 ( の数が多い閉路 \(C_2\) を \(1\) つ取ります。 \(C_1\) はすべての辺を \(1\) 度以上用いているため、 \(C_1\) から \(C_2\) に用いられている辺を除く、ということができます。この後残っている分についてはいくつかのオイラー閉路に分けることができます。これらに含まれている ) の数は ( の数より多いです。特にオイラー閉路のいずれかにおいては ) の数が ( の数より多くなっており、これは最初の仮定に反しています。

以上の考察から問題は \(2\) 種類の閉路の存在判定に帰着されました。前者についてははラベルが ) である辺に重み \(1\) 、( である辺に重み \(-1\) を付与したグラフにおける負閉路の存在判定であり、ベルマンフォード法により \(O(NM)\) 時間で計算でき、十分高速です。後者についても重みを逆にすればいいです。