565.array-nesting.md

并查集

$f[N]$ 初始化 $0,...,N-1$

嵌套规则：$i，A[i]$ 两点合并

代码实现

class Solution {
public:
    int f[200010];
    int cnt[200010];
    int find(int x){
        if (f[x] == x) return x;
        return f[x] = find(f[x]);
    }

    void u(int x, int y){
        int p = find(x), q = find(y);
        if (p == q) return;
        f[q] = p;
        cnt[p] += cnt[q];
    }

    int arrayNesting(vector<int>& A) {
        int n = A.size();
        // memset(cnt, 1, sizeof(cnt));
        for (int i =0; i <n; i++) {
            f[i] = i;
            cnt[i] = 1;
        }

        for (int i =0; i< n; i++){
            u(i, A[i]);
        }

        int res = 0;
        for (int i = 0; i < n; i++){
            res = max(res, cnt[i]);
        }

        return res;
    }
};