No.483 マッチ並べ - yukicoder
無向グラフの辺を有向化する。その時→←のような辺があるかどうか判定せよ。
以前解いたときはN=100かつ条件を満たす探索の枝刈りがとても効率いいので、単なる自然なdfsの全探索で通してしまった。
ループが2個以上あるときは不可なので、平面グラフのオイラーの定理を使う。
ループの数 = 2 - 頂点数 + 辺の数 ≦ 1
∴頂点数 - 辺の数 ≧ 1
をチェックすれば良い。逆に言うと平面グラフ性の判定はオイラーの定理を使う、というのを覚えておきたい。
