Codeforces AIM Tech Round (Div. 1) A. Graph and String
悲しいことにシステムテストで落ちた。
解法
n-1 本辺が生えている頂点は b にするのが最適。b を取り除いたグラフの連結成分の個数が 2 個以下で、かつそれらが完全グラフになっていれば構成可能。
同じ文字を持つ頂点同士は結ばれている必要があるので完全性は不可欠。
連結成分は BFS や Union-Find で求まる。
Codeforces AIM Tech Round (Div. 1) A. Graph and St ...
0完でレートが瀕死…。