2018-2019 ACM-ICPC, Asia Seoul Regional Contest I 問題 - のいみのいみのいみのいみ

かなり面白かった + 解説が韓国語しかないということで簡潔に解法をメモっておきます。

概要

木 $G$ がある。 $G$ で距離 $2$ の点の組に辺を張ったグラフ $G ^ 2$ が与えられる。 $G$ を 1 つ復元、またはそのような $G$ がないことを言え。

制約

$N \le10 ^ 5$
$M\le10 ^ 6$

かなり取っ掛かりがつきにくくて迷走した。

$G$ での次数を「真次数」、 $G ^ 2$ での次数を単に「次数」という。次数は、 $G$ での隣接頂点の真次数の和になる。

ある頂点 $u$ を取り、 $u$ の $G ^ 2$ での隣接頂点の誘導部分グラフを考える。 $u$ 自身は含めないことに注意。

この誘導グラフの形を観察すると、中心に完全グラフがあり、その完全グラフの各頂点にこれまた完全グラフがくっついている形になっていることがわかる。中心の完全グラフが、 $u$ の $G$ での隣接頂点になっている。

誘導グラフが完全グラフ一つのみからなったり、二つのみからなったりする場合もあるが、結局はすべての極大完全グラフの頂点を含むような完全グラフの頂点が、 $u$ の隣接頂点である。これは、二重頂点連結成分分解をして関節点全部を含むような二重頂点連結成分を探せばよい。(実は完全グラフ 2 個の場合はどちらを取っても OK！)

$(u, v)$ という辺があったことがわかったとする。 $v$ の $G ^ 2$ での隣接頂点のうち、 $u$ の $G ^ 2$ での隣接頂点であり $u$ の $G$ での隣接頂点でない頂点集合が、 $v$ の $G$ での隣接頂点である。以下それを再帰的にやればよい。

提出コード

感想

難しくて面白いかなりいい問題だった。一つの頂点に着目したときに完全グラフが～みたいなのは自然にたどり着く発想ではあったが、それ自身を除くという発想がなかなか出てこなかったし出てきても試そうとしていなかった。解法ガチャを回すうちにたどり着ける考察では明らかにあるので時間を短縮できるように頑張りたい、一個一個の解法候補を詰める速度を早くするのがいいのかなあ