library-checker-problems [問題案]Unionfind(unionfind)

[問題案]Unionfind(unionfind)

Open yosupo06 opened this issue 5 years ago • 2 comments

Sep 13 '19 08:09 yosupo06

経路圧縮のみのやつのworst case、Rankのみのやつ(あとRankの代わりに重みを使うやつ)のworst caseを用意する

経路圧縮のみのやつは http://www.csd.uwo.ca/~eschost/Teaching/07-08/CS445a/p245-tarjan.pdf に乗ってるかな(フィボナッチ数みたいなイメージの変な木の構築だったはず)

両方のやつの最悪ケース(\alphaかかるやつ)は、いるかな…？

Mar 15 '20 14:03 yosupo06

UnionFindの各要素の連結成分のサイズを取得するクエリもverifyしたい．これは別の問題として切り出しても良い気がします．

Jun 13 '20 07:06 hec12

別問題の提案がすでにあるので、close

Mar 26 '23 16:03 maspypy

https://judge.yosupo.jp/problem/unionfind のforumはここを指していそう？ ←ぼーっとしてました　気にしないでください

Mar 26 '23 16:03 yosupo06