题目描述

不写了

算法

并查集

直接一个并查集的模板题。

坑点1

有一个数据量达到 2e5 的测试用例，考察了并查集的层次问题。这个数据就是 $1$ 的父亲是 $2$；$2$ 的父亲是 $3$；…；以此类推；$199999$ 的父亲是 $200000$；$200000$ 的父亲是自己。
按照并查集模板，这样我们将建立一个层数为 $199999$ 的单边树，在查找父亲的时候，使用递归实现就会拿到 TLE 奖励。恭喜，我中奖了。
因此，我们需要进行层数优化，我是增加了一个 rank 数组。

坑点2

也是由于增加了数组 rank，导致在 AcWing 这里编译出现重名。只能将 rank 改为 urank。

时间复杂度

$O(T*N)$。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=2e5+10;
int parent[MAXN];//父亲
int urank[MAXN];//层数 
int s[MAXN];//集合元素个数
int n;

//初始化 
void init() {
    for (int i=1; i<=n; i++) {
        parent[i]=i;
        urank[i]=0; 
        s[i]=1;
    }
} 

//查询父亲 
int root(int x) {
    if (parent[x]==x) {
        return x;
    }
    return root(parent[x]);
}

void union_set(int x, int y) {
    int x_root=root(x);
    int y_root=root(y);
    if (x_root!=y_root) {
        if (urank[x_root]>urank[y_root]) {
            parent[y_root]=x_root;
            s[x_root]+=s[y_root];           
        } else if (urank[x_root]<urank[y_root]) {
            parent[x_root]=y_root;
            s[y_root]+=s[x_root];
        } else {
            parent[y_root]=x_root;
            s[x_root]+=s[y_root];           
            urank[x_root]++;            
        }
    }
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);

        init();
        for (int i=1; i<=n; i++) {
            int v;
            scanf("%d", &v);
            union_set(i, v);
        }
        for (int i=1; i<=n; i++) {
            printf("%d ", s[root(i)]);
        }
        printf("\n");
    }

    return 0;
}