#include <iostream>
#include <memory>
#include <vector>
#include <ctime>

static const uint64_t SEED = 0xDEADBEEFull;
static const size_t ROWS = 10000;
static const size_t COLS = 10000;
static const uint32_t COLORS_NUM = 3;

uint32_t LCGRand()
{
    static uint64_t seed = SEED;
    seed = seed * 6364136223846793005 + 1442695040888963407;
    return seed >> 32;
}

struct Block {
    typedef std::shared_ptr<Block> Ptr;

    uint32_t color;
    size_t size;
    Ptr redir;
};

int main()
{
    std::vector<Block::Ptr> up_row(COLS);
    size_t max_size = 0;

    clock_t start = clock();
    for (size_t row = 0; row < ROWS; row++) {
        Block::Ptr left;

        for (size_t col = 0; col < COLS; col++) {
            uint32_t color = LCGRand() % COLORS_NUM;

            Block::Ptr &up = up_row[col];
            while (up && up->redir)
                up = up->redir;

            Block::Ptr cur;
            if (left && (left->color == color)) {
                cur = left;

                if (up && (up->color == color) && (up != left)) {
                    left->size += up->size;
                    up->redir = left;
                }
            } else if (up && (up->color == color)) {
                cur = up;
            } else {
                cur = std::make_shared<Block>(Block{ color, 0, nullptr });
            }

            max_size = std::max(max_size, ++cur->size);
            left = up = cur;
        }
    }

    std::cout << "Max block size: " << max_size << std::endl
        << "Time: " << (clock() - start) / (CLOCKS_PER_SEC / 1000) << " ms" << std::endl;
    return 0;
}