辺を頂点にして二部グラフ

グラフは辺(やそれに類する頂点間の関係)を頂点にして二部グラフにすることができる

連結成分を求める上ではそれでも良い

https://gyazo.com/c7b9a05ea68b75db5e9f55b7f68cf36a

陽に辺を構築することが高コストな時にこの変換が有益

例えば「頂点が長さMの数列を持っていて、二頂点の数列に共通の数がある時に辺が引かれる」

O(V^2M)のコストが掛かる

数も頂点にするとO(VM)

頂点数は増えるが、UnionFindはほぼ定数オーダーなので重要でない

辺の数が少なくなるとは一般には言えない