站外题，好像要用并查集，但蒟蒻不会

题目总版

Tgdoem @ 2024-10-06 16:02:51

给定一个1-N的排列A[1],A[2],…A[N]，定义集合S[K]={A[K],A[A[K]],A[A[A[K]]] ...}。

显然对于任意的K=1..N，S[K]都是有限集合。 你能求出其中包含整数最多的S[K]的大小吗？

输入格式

第一行包含一个整数N。(1≤N≤100000)

第二行包含N个两两不同的整数，A[1],A[2],…A[N]。(1≤A[i]≤N)

输出格式

最大的S[K]的大小。

输入

7 6 5 1 4 2 7 3

输出

4

by Lisuyang @ 2024-10-06 16:20:19

@Tgdoem

你看看行不行

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 6;
int ds[N], n, ans = 0;
int find(int x){ return ds[x] < 0 ? x : ds[x] = find(ds[x]); }
void merge(int x, int y){
    x = find(x), y = find(y);
    if(x == y) return;
    if(ds[x] < ds[y]) swap(x, y);
    ds[y] += ds[x], ds[x] = y;
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i) ds[i] = -1;
    for(int i = 1, x; i <= n; ++ i){
        scanf("%d", &x);
        merge(i, x);
    }
    for(int i = 1, x; i <= n; ++ i){
        if(ds[i] < 0) ans = max(ans, -ds[i]);
    }
    printf("%d", ans);
    return 0;
}

by Tgdoem @ 2024-10-06 16:45:21

@Lisuyang 可以，谢谢

|