funplus9.21笔试

唯一编程题

给出n个三角形的端点序号，询问重合三角形的最大集合有多少个三角形？

依次计算两两之间的关系，使用并查集获取连通块求解

int maxConnectedTrianglesSize(vector<vector<int> >& indexArray, int n) {  
    vector<int> f(n);  
    for (int i = 0; i < n; i++) {  
        f[i] = i;  
    }  
    function<int(int)> findx = [&](int y) {  
        if (f[y] == y) return y;  
        else return f[y] = findx(f[y]);  
    };  
    function<void(int, int)> merge = [&](int a, int b) {  
        int xa = findx(a), xb = findx(b);  
        if (xa == xb) return;  
        f[xa] = xb;  
    };  
    function<bool(vector<int>, vector<int>)> check = [&](vector<int> a, vector<int>b) {  
        unordered_map<int, int> mp;  
        int tmp = 0;  
        for (int i:a) {  
            mp[i] = 1;  
        }  
        for (int i:b) {  
            if (mp.count(i)) tmp++;  
        }  
        if (tmp >= 2) return true;  
        else return false;  
    };  
    for (int i = 0; i < n; i++) {  
        for (int j = i + 1; j < n; j++) {  
            if (check(indexArray[i],indexArray[j])) merge(i,j);  
        }  
    }  
    unordered_map<int, int> t;  
    int res = 0;  
    for (int i = 0; i < n; i++) {  
        if (t.count(findx(i))) t[findx(i)] += 1;  
        else t[findx(i)] = 1;  
        res = max(res, t[findx(i)]);  
    }  
    return res;  
}