美团8.12笔试

给你一个长度为n的字符串，然后你可以将其分为x*y = n的二维数组，当四个方向字符相同时为联通块，求最小的连通块个数。

只过了20%，求各位佬指点一下：

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class UFSets {
public:
    vector<int> vec;

    UFSets(int sz) {
        vec = vector<int>(sz, -1);
    }

    int Find(int x) {
        while (vec[x] > 0)x = vec[x];
        return x;
    }

    bool Union(int root1, int root2) {
        int r1 = Find(root1);
        int r2 = Find(root2);
        if (r1 == r2) {
            return false;
        }
        if (vec[r1] < vec[r2]) {
            vec[r2] = vec[r1] + vec[r2];
            vec[r1] = r2;
        }
        else {
            vec[r1] = vec[r1] + vec[r2];
            vec[r2] = r1;
        }
        return true;
    }
};

int main() {
    int n;
    cin >> n;
    string str;
    cin >> str;
    int minNumSets = 0x3f3f3f3f;
    // x=1 与 y=1效果一致，因此y直接从2开始就好了
    for (int x = 1; x < n / 2; x++) {
        if (n % x == 0) {
            int y = n / x;
            UFSets ufs(n);
            for (int i = 0; i < n; i++) {
                int posX = i / y;
                int posY = i % y;
                // 上边
                if (posX - 1 >= 0 && str[(posX-1)*x+posY] == str[i]) {
                    // 合并
                    ufs.Union((posX - 1) * x + posY, i);
                }
                // 左边
                if (posY - 1 >= 0 && str[posX * x + posY - 1] == str[i]) {
                    // 合并
                    ufs.Union(posX * x + posY - 1, i);
                }
            }
            // 检查ufs中的集合数量
            int numSets = 0;
            for (int i = 0; i < ufs.vec.size(); i++) {
                if (ufs.vec[i] < 0) {
                    numSets++;
                }
            }
            if (numSets < minNumSets) {
                minNumSets = numSets;
            }
        }
    }

    cout << minNumSets;
    return 0;
}
// 64 位输出请用 printf("%lld")