参考文献
https://www.acwing.com/solution/content/113488/
java代码
import java.util.Scanner;
//思路:只有和0连接的牛才不会产生闭环
//并查集找到它的父节点
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int[] F = new int[n+1];
for (int i = 1; i < F.length; i++) {
F[i] = input.nextInt();
}
//2.并查集
int[] num = new int[n+1];
//3.初始情况指针都指向自己
for (int i = 0; i < num.length; i++) {
num[i] = i;
}
//4.将连接的地方加入
for (int i = 1; i < F.length; i++) {
join(i,F[i],num);
}
//5.遍历数组,查找根节点是0的,那么它就不是闭环
int ans = 0;
for (int i = 1; i < F.length; i++) {
//再找一遍根节点,判断根节点是否为0
if (find(num[i],num) == 0)ans++;
}
System.out.println(ans);
}
static void join(int a,int b,int[] num){
//1.找到两个的根节点
int Ga = find(a,num);
int Gb = find(b,num);
//2.将两个根节点指向同一个节点
num[Ga] = Gb;
}
static int find(int n,int[] num){
int cet = n;
//1.先找出自己的父亲节点,在找父亲的父亲节点,一直找到根节点
while (n != num[n]){
n = num[n];
}
//2.将当前节点的根节点设置为当前节点的父亲节点
num[cet] = n;
//3.返回找到的根节点
return n;
}
}