AcWing 3579. 数字移动    原题链接    困难

作者： 作者的头像   垫底抽风 ,  2021-05-29 20:15:30 ,  所有人可见 ,  阅读 1590

27


算法

(dfs,爆搜)

考虑将排列看成一张图，其中点 $i$ 向点 $p _ i$ 连边。

那么一个排列在图上一定是很多个环。

而每个数字第一次回到自己的次数，就是其所在环的长度。

对于每个点，爆搜其所在环，求出环长，将答案扔到环中所有点上。

时间复杂度

$\text{dfs}$ 中会将所有点都枚举一次，故复杂度为 $O(n)$。

C++ 代码

#include <cstdio>
#include <cstring>

const int N = 200005;

int n, p[N], res[N];
bool st[N];
int xs[N], sz;

// 返回 x 所在环长
int dfs(int x) {
    if (st[x]) return 0;
    st[x] = true;
    xs[sz++] = x; // 将环上所有点存到一个数组中
    return dfs(p[x]) + 1;
}

int main() {
    int task;
    for (scanf("%d", &task); task--; ) {
        scanf("%d", &n);
        memset(st, false, sizeof st);
        for (int i = 1; i <= n; ++i) scanf("%d", p + i);

        for (int i = 1; i <= n; ++i)
            if (!st[i]) {
                int t = dfs(i);
                for (int k = 0; k < sz; ++k) res[xs[k]] = t;
                sz = 0;
            }

        for (int i = 1; i <= n; ++i) printf("%d ", res[i]);
        puts("");
    }

    return 0;
}

1 评论

用户头像
大瓜娃子   2023-01-11 16:31         踩      回复

贴一个python的
## 并查集求连通块大小

case = int(input())

def find(x):
    if p[x] != x: p[x] = find(p[x])
    return p[x]

for _ in range(case):
    n = int(input())
    N = n + 10
    p = [i for i in range(n+1)]
    size = [1] * N
    pos = [0] + list(map(int,input().split()))

    for i in range(1,n+1):
        a,b = find(i),find(pos[i])
        if a != b:
            #先累计，后合并。合并了再加和 就不是原来的值了
            size[a] += size[b]
            p[b] = a #将b的父节点换成a
    for k in range(1,n+1):
        print(size[find(k)],end=" ")
    print()

### 直接模拟 + 剪枝优化

case = int(input())

for _ in range(case):
    n = int(input())
    N = n + 10
    a = [0] + list(map(int,input().split()))

    ans = [0] * (n + 1)

    for i in range(1,n+1): 
        if ans[i] != 0:
            continue
        y = a[i] # 5
        h = [i] # 1
        cnt = 1
        while y != i: 
            h.append(y)
            y = a[y]
            cnt += 1
        # ans[i] = cnt 暴力过了7/10数据
        for x in h:
            ans[x] = cnt
    for i in range(1,n+1): print(ans[i],end=" ")
    print()