重新排列奶牛

C++

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], b[N], p[N], s[N];
int find(int x)
{
    if(p[x] != x)p[x] = find(p[x]);
    return p[x];
}
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++)cin >> a[i];
    for(int i = 1; i <= n; i ++)
    {
        int x;
        cin >> x;
        b[x] = i;
    }
    for(int i = 1; i <= n; i ++)p[i] = i, s[i] = 1;
    for(int i = 1; i <= n; i ++)
    {
        int x = a[i], y = a[b[x]];
        if(find(x) != find(y))
        {
            s[find(y)] += s[find(x)];
            p[find(x)]  = find(y);
            
        }
    }
    int cnt = 0, mx = 0;
    for(int i = 1; i <= n; i ++)
    {
        if(find(i) == i && s[i] > 1)
        {
            cnt ++;
            mx = max(s[i], mx);
        }
    }
    if(!cnt)mx = -1;
        cout << cnt << " "<<mx<<endl;
    
}

Java

import java.util.*;
public class Main{
    public static int N = 110;
    public static int[] a = new int[N];
    public static int[] b = new int[N];
    public static int[] p = new int[N];
    public static int[] s = new int[N];
    public static void main(String[] args){
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        for(int i = 1; i <= n; i ++)a[i] = cin.nextInt();
        for(int i = 1; i <= n; i ++)
        {
            int x = cin.nextInt();
            b[x] = i;
        }
        for(int i = 1; i <= n; i ++){
            p[i] = i;
            s[i] = 1;
        }
        for(int i = 1; i <= n; i ++)
        {
            int x = a[i], y = a[b[x]];
            if(find(x) != find(y))
            {
                s[find(y)] += s[find(x)];
                p[x] = find(y);
            }
        }
        int cnt = 0, mx = 0;
        for(int i = 1; i <= n; i++)
        {
            if(s[i] > 1 && find(i) == i)
            {
                cnt ++;
                if(mx < s[i])mx = s[i];
            }
        }
        if(cnt == 0)mx = -1;
        System.out.println(cnt + " " + mx);
    }
    public static int find(int x)
    {
        if(p[x] != x)p[x] = find(p[x]);
        return p[x];
    }
}