DSU

#include <iostream>
#include <vector>

class DSU {
public:
    explicit DSU( int n );

    int Find( int u );
    void Merge( int u, int v );

private:
    std::vector<int> parent;
    std::vector<int> rank; // Ранги узлов. Глубина дереве не больше ранга.
};

DSU::DSU( int n ) :
    parent( n ),
    rank( n, 1 )
{
    for( int i = 0; i < n; ++i ) {
        parent[i] = i;
    }
}

int DSU::Find( int u )
{
    if( parent[u] == u ) {
        return u;
    }
    // Сжатие пути.
    return parent[u] = Find( parent[u] );
}

void DSU::Merge( int u, int v )
{
    const int rootU = Find( u );
    const int rootV = Find( v );
    if( rank[rootU] < rank[rootV] ) {
        parent[rootU] = rootV;
    } else {
        if( rank[rootU] == rank[rootV] ) {
            ++rank[rootU];
        }
        parent[rootV] = rootU;
    }
}

int main()
{
    DSU dsu( 5 );
    std::cout << ( dsu.Find( 0 ) != dsu.Find( 2 ) ? "OK" : "FAIL" ) << std::endl;
    dsu.Merge( 0, 2 );
    std::cout << ( dsu.Find( 0 ) == dsu.Find( 2 ) ? "OK" : "FAIL" ) << std::endl;
    dsu.Merge( 4, 2 );
    std::cout << ( dsu.Find( 0 ) == dsu.Find( 4 ) ? "OK" : "FAIL" ) << std::endl;
    dsu.Merge( 1, 3 );
    std::cout << ( dsu.Find( 1 ) == dsu.Find( 3 ) ? "OK" : "FAIL" ) << std::endl;
    std::cout << ( dsu.Find( 1 ) != dsu.Find( 4 ) ? "OK" : "FAIL" ) << std::endl;
    dsu.Merge( 1, 4 );
    std::cout << ( dsu.Find( 1 ) == dsu.Find( 4 ) ? "OK" : "FAIL" ) << std::endl;
    return 0;
}