読者です 読者をやめる 読者になる 読者になる

アルゴリズム忘備録

競技プログラミングとかデータ分析とか

Yukicoder 483 マッチ並べ

No.483 マッチ並べ - yukicoder

 

無向グラフの辺を有向化する。その時→←のような辺があるかどうか判定せよ。

 

以前解いたときはN=100かつ条件を満たす探索の枝刈りがとても効率いいので、単なる自然なdfsの全探索で通してしまった。

 

ループが2個以上あるときは不可なので、平面グラフのオイラーの定理を使う。

ループの数 = 2 - 頂点数 + 辺の数 ≦ 1

∴頂点数 - 辺の数 ≧ 1

 

をチェックすれば良い。逆に言うと平面グラフ性の判定はオイラーの定理を使う、というのを覚えておきたい。