スーパー頂点を用いてグラフの辺数を削減するテク
概要
辺が密なグラフの場合、幅優先探索するとTLEになることがある
頂点v1, v2, ..., vN間のすべてに辺がある場合、スーパー頂点を1個用意することで辺数を削減できる
https://github.com/E869120/kyopro_educational_90/blob/main/editorial/054.jpg
の画像を参照
実装
スーパーノードM個を用意して、N個の頂点の後ろに加える
code:cpp
参考URL
https://github.com/E869120/kyopro_educational_90/blob/main/editorial/054.jpg
https://drken1215.hatenablog.com/entry/2023/06/10/130500