Union Find data structure for Disjoint-Set, O(\alpha(n))

union_find.cc

#define MAXU    100000

struct UnionFind {
    int f[MAXU];
    int rank[MAXU];

    void clear() {
        memset(f, -1, sizeof(f));
        memset(rank, 0, sizeof(rank));
    }

    inline int root(int x) {
        int y = x;
        for (; f[x] != -1; x = f[x]);
        while (y != x) {
            int next = f[y]; f[y] = x;
            y = next;
        }
        return x;
    }

    int find(int x, int y) {
        return (root(x) == root(y));
    }

    void merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return;
        if (rank[x] < rank[y])
            f[x] = y;
        else {
            f[y] = x;
            if (rank[x] == rank[y]) ++ rank[x];
        }

    }
};