Quick Find
概略
同一集合かの判定が$ O(1)、集合のマージが$ O(\log N)で可能
どのアイテムがどのグループかを一次元配列、 各グループがどのitemを持ってるかを二次元配列で持つ
グループはn個で、マージする際は要素を全部新しいグループに流し込む
計算量
マージが最悪$ O(N)っぽいけど、小さい方を大きい方に流し込めば$ O(log N)
マージ後のサイズは倍以上になることが保証されているため、各アイテムは高々$ log N回しか移動しない
実装例
code:QuickFind.cpp
class QuickFind
{
template <class kizuna>
using akari = vector<kizuna>;
template <class yuzuki>
using yukari = akari<akari<yuzuki>>;
int n;
akari<int> i2g; //item to group
yukari<int> g2i; //group to item
public:
QuickFind(int n_) : n(n_)
{
i2g.resize(n_);
g2i.resize(n_);
for (int i = 0; i < n_; i++)
{
}
}
void merge(int x, int y)
{
//gxにgyをマージ
int gx = i2gx, gy = i2gy; //これぞマージテクの真髄...
if (g2igx.size() < g2igy.size()) {
swap(gx, gy);
}
{
}
g2igx.insert(g2igx.end(), g2igy.begin(), g2igy.end()); }
inline bool same(int x, int y)
{
}
};