O(α(N)) for UnionFind operations?

#include <iostream>
#include <unordered_map>
#include <functional>
#include <vector>
#include <time.h>
#include <map>
#include <random>

using namespace std;

class UF
{
public:
    UF()
    {

    }
    UF( int size )
    {
        parents.reserve(size);
        ranks.reserve(size);
        for( int i = 0; i < size; i++ )
        {
            parents.push_back(parents.size());
            ranks.push_back(0);
        }
    }
    void reserve( int size )
    {
        parents.reserve(size);
        ranks.reserve(size);
    }
    int makeset()
    {
        int val = parents.size();
        parents.push_back(val);
        ranks.push_back(0);
        return val;
    }
    bool sameset( int elem1, int elem2 )
    {
        if(elem1 >= parents.size() || elem2 >= parents.size() )
        {
            // ERR
            return false;
        }
        return find(elem1) == find(elem2);
    }
    int find( int elem )
    {
        if(elem >= parents.size() )
        {
            // ERR
            return -1;
        }

        if( parents[elem] != elem )
        {
            parents[elem] = find( parents[elem] );
        }
        return parents[elem];
    }
    void merge( int elem1, int elem2 )
    {
        if(elem1 >= parents.size() || elem2 >= parents.size() )
        {
            // ERR
            return;
        }

        int root1 = find(elem1);
        int root2 = find(elem2);

        if( root1 == root2 )
            return;

        if( ranks[root1] < ranks[root2] )
        {
            parents[root1] = root2;
        } else if( ranks[root2] < ranks[root1] )
        {
            parents[root2] = root1;
        } else
        {
            parents[root2] = root1;
            ranks[root1]++;
        }
    }
private:
    vector<int> parents;
    vector<int> ranks;
};

int main()
{
    int N = 10'000'000;
    int M = 10'000'000;

    auto dice = bind ( uniform_int_distribution<int>(0,N-1), mt19937(random_device()()) );
    UF unionfind;
    clock_t t1;
    clock_t t2;
    vector<int> randnums(N+4*M);
    for( int i = 0; i < randnums.size(); i++ )
        randnums[i] = dice();
    auto it = randnums.begin();

    t1 = clock();
    for( int i = 0; i < N; i++ )
        unionfind.makeset();
    t2 = clock();
    cout << "MAKESET: " << (t2-t1)/(float)CLOCKS_PER_SEC << endl;

    t1 = clock();
    for( int i = 0; i < M; i++ )
    {
        unionfind.find( *(++it) );
    }
    t2 = clock();
    cout << "FIND: " << (t2-t1)/(float)CLOCKS_PER_SEC << endl;

    t1 = clock();
    for( int i = 0; i < M; i++ )
    {
        unionfind.merge( *(++it), *(++it) );
    }
    t2 = clock();
    cout << "MERGE: " << (t2-t1)/(float)CLOCKS_PER_SEC << endl;

    t1 = clock();
    for( int i = 0; i < M; i++ )
    {
        unionfind.find( *(++it) );
    }
    t2 = clock();
    cout << "FIND AGAIN: " << (t2-t1)/(float)CLOCKS_PER_SEC << endl;

    t1 = clock();
    for( int i = 0; i < M; i++ )
    {
        unionfind.find( *(++it) );
    }
    t2 = clock();
    cout << "FIND AGAIN2: " << (t2-t1)/(float)CLOCKS_PER_SEC << endl;

    return 0;
}

/*
N = 100'000
MAKESET: 0.001002
FIND: 0.037006
MERGE: 0.098528
FIND AGAIN: 0.048562
FIND AGAIN2: 0.000534

N = 1'000'000
MAKESET: 0.011646
FIND: 0.054282
MERGE: 0.352768
FIND AGAIN: 0.153535
FIND AGAIN2: 0.012702

N = 10'000'000
MAKESET: 0.16386
FIND: 0.319329
MERGE: 3.45287
FIND AGAIN: 0.532275
FIND AGAIN2: 0.472613

N = 1'000'000
M = 1'000'000
MAKESET: 0.010744
FIND: 0.005321
MERGE: 0.101198
FIND AGAIN: 0.013164
FIND AGAIN2: 0.009081

MAKESET should be O(N), the rest should be O(M α(N)), but this appears to not be the case.
*/

/* a more general Union-Find data structure, but unordered_map is super slow
template <typename T>
class UF
{
public:
    UF<T>()
    {

    }
    UF<T>( const vector<T>& init )
    {
        compression.reserve(init.size());
        parents.reserve(init.size());
        ranks.reserve(init.size());
        for( const T& i : init )
        {
            compression[i] = parents.size();
            parents.push_back(parents.size());
            ranks.push_back(0);
        }
    }
    void reserve( int size )
    {
        compression.reserve(size);
        parents.reserve(size);
        ranks.reserve(size);
    }
    void makeset( const T& set )
    {
        if( compression.count(set) == 1 )
            return; // Err, already exists
        compression[set] = parents.size();
        parents.push_back(parents.size());
        ranks.push_back(0);
    }
    bool sameset( const T& set1, const T& set2 )
    {
        return find(set1) == find(set2);
    }
    int find( const T& set )
    {
        if( compression.count(set) == 0 )
            return -1; // Err, not in set
        return rawfind(compression[set]);
    }
    void merge( const T& set1, const T& set2 )
    {
        if( compression.count(set1) == 0 || compression.count(set2) == 0 )
            return; // Err, not in set

        int comprSet1 = compression[set1];
        int comprSet2 = compression[set2];

        int root1 = find(set1);
        int root2 = find(set2);

        if( root1 == root2 )
            return;

        if( ranks[root1] < ranks[root2] )
        {
            parents[root1] = root2;
        } else if( ranks[root2] < ranks[root1] )
        {
            parents[root2] = root1;
        } else
        {
            parents[root2] = root1;
            ranks[root1]++;
        }
    }
    void print()
    {
        cout << "[ ";
        for( auto it = compression.begin(); it != compression.end(); it++ )
        {
            auto it2 = it;
            it2++;
            cout << "(" << it->first << ":" << it->second << ")" << (it2 == compression.end() ? " " : ", ");
        }
        cout << "]\n";
        printArr(parents);
        printArr(ranks);
    }
private:
    void printArr( const vector<int>& arr )
    {
        cout << "[ ";
        for( auto it = arr.begin(); it != arr.end(); it++ )
        {
            cout << *it << (it + 1 == arr.end() ? " " : ", ");
        }
        cout << "]\n";
    }
    int rawfind( const int set )
    {
        if( parents[set] != set )
            parents[set] = rawfind( parents[set] );
        return parents[set];
    }
    unordered_map<T,int> compression;
    vector<int> parents;
    vector<int> ranks;
};
*/