union find tree

uft.d

struct UF
{
    ptrdiff_t[] parent;
    size_t n;
    this (size_t n)
    {
        parent.length = this.n = n;
        foreach (i; 0..n)
            parent[i] = -1;
    }
    void unite(ptrdiff_t x, ptrdiff_t y)
    {
        import std.algorithm : swap;
        x = find(x);
        y = find(y);
        if (x == y)
            return;
        if (parent[x] < parent[y])
            swap(x, y);
        parent[y] += parent[x];
        parent[x] = y;
    }
    ptrdiff_t find(ptrdiff_t x)
    {
        if (parent[x] < 0)
            return x;
        return parent[x] = find(parent[x]);
    }
    bool same(ptrdiff_t x, ptrdiff_t y)
    {
        return find(x) == find(y);
    }
    auto sets()
    {
        ptrdiff_t[][ptrdiff_t] ret;
        foreach (i; 0..n)
        {
            auto key = find(i);
            if (auto val = key in ret)
                *val ~= i;
            else
                ret[key] = [i];
        }
        return ret;
    }
}

unittest
{
    import std.stdio;
    import std.algorithm : schwartzSort;
    import std.random : uniform;

    auto n = UF(100);
    foreach (i; 0..50)
        n.unite(uniform(0, 50), uniform(50, 100));
    foreach (l; n.sets().values.schwartzSort!(v => -v.length)())
        l.writeln();
}