辺を頂点にして二部グラフ
- グラフは辺(やそれに類する頂点間の関係)を頂点にして二部グラフにすることができる
- 連結成分を求める上ではそれでも良い
- 陽に辺を構築することが高コストな時にこの変換が有益
- 例えば「頂点が長さMの数列を持っていて、二頂点の数列に共通の数がある時に辺が引かれる」
- O(V^2M)のコストが掛かる
- 数も頂点にするとO(VM)
- 頂点数は増えるが、UnionFindはほぼ定数オーダーなので重要でない
- 辺の数が少なくなるとは一般には言えない
- 少なくなる制約がついてたケース codefestival_2016_final_c
- 例えば「頂点が長さMの数列を持っていて、二頂点の数列に共通の数がある時に辺が引かれる」
