题面

核心思想

这道题跟树没有任何关系。。。

样例的 2 1 4 3 直接在数组交换为 1 2 3 4 就可以了。
那么只要当前下标i 与 nums[i] 不相等我们就交换
比如

5 1 2 3 4
1 != 5 交换为 -> 4 1 2 3 5
1 != 4 交换为 -> 3 1 2 4 5
1 != 3 交换为 -> 2 1 3 4 5
1 != 2 交换为 -> 1 2 3 4 5

第3题也很简单懒得写了。

代码

import java.util.*;

public class Main {
    static final int MAXN = (int) (1e4 + 10);

    public static void main(String[] args) {
        final long MOD = (long) (1e9 + 7);

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n + 1];
        int cnt = 0;
        for(int i = 1; i <= n; i++){
            nums[i] = in.nextInt();
        }
        for(int i = 1;i <= n; i++){
            while(nums[i] != i){
                int tmp = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = tmp;
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}