pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces AIM Tech Round (Div. 1) A. Graph and String

悲しいことにシステムテストで落ちた。

codeforces.com

解法

n-1 本辺が生えている頂点は b にするのが最適。b を取り除いたグラフの連結成分の個数が 2 個以下で、かつそれらが完全グラフになっていれば構成可能。

f:id:pekempey:20160205150029p:plain:w350

同じ文字を持つ頂点同士は結ばれている必要があるので完全性は不可欠。


連結成分は BFS や Union-Find で求まる。

Codeforces AIM Tech Round (Div. 1) A. Graph and St ...

0完でレートが瀕死…。