parukii https://blog.hatena.ne.jp/parukii/ parukiのブログ https://par.hateblo.jp/ 各座標を頂点としてグラフを書く。連結成分ごとに考えてみる。 グラフが木になる場合は、根付き木と見なして親から子へ、マッチの頭薬を向けて並べていけばいい。 グラフが閉路を1個だけもつ場合。まず、その1個の閉路を、片方向（時計回り、反時計回りどちらでも)にならべていく。そうしたら、先の方法と同様に、サイクルを根付き木の根と見なして残りのマッチを並べていけばいい。 グラフが閉路を2個以上もつ場合はこれらの埋め方は不可。 閉路が2個以上あるかどうかの判定は次数の合計を見ればいい。 次数/2 = 頂点数-1 のときは木 次数/2 = 頂点数 のときは閉路1個 次数/2 > 頂点数 のときは閉路2個以上 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpar.hateblo.jp%2Fentry%2F2017%2F02%2F13%2F134241" title="yukicoder #483: マッチ並べ - parukiのブログ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/p/parukii/20170213/20170213134222.jpg Hatena Blog https://hatena.blog 2017-02-13 13:42:41 rich https://par.hateblo.jp/entry/2017/02/13/134241 1.0 100%