PolandBall & Forest

Explicación

Concentrémonos primero en un árbol y su diámetro, llamando $E_1$ y $E_2$ a los dos extremos. Para cada vértice $v$ de este árbol, $p[v]$ es igual a $E_1$ o a $E_2$ , como se puede demostrar aquí .

Además, aunque el árbol tenga varios diámetros, solo se toman los puntos con el ID más bajo, de modo que siguen apareciendo dos puntos únicos por cada árbol.

Así, podemos contar la cantidad de vértices distintos en $P$ y dividir por dos para hallar la cantidad de árboles, teniendo cuidado de contar el caso $P[i]$ = $i$ como un árbol, porque es un vértice aislado que cuenta como un solo árbol.

Implementación

Complejidad temporal: $\mathcal{O}(N)$

C++PythonJava


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n;
	cin >> n;
	// Arreglo que guarda si los vértices fueron visitados
	vector<bool> visited(n);
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		if (i + 1 == num) ans += 2;
		else if (!visited[num - 1]) {
			ans++;
			visited[num - 1] = 1;
		}
	}
	cout << ans / 2 << '\n';
}


n = int(input())
nums = list(map(int, input().split()))
 
# Arreglo que guarda si los vértices fueron visitados
visited = [False] * n
ans = 0
 
for i in range(n):
	if i + 1 == nums[i]:
		ans += 2
	elif not visited[nums[i] - 1]:
		ans += 1
		visited[nums[i] - 1] = True
 
print(ans // 2)


import java.io.*;
import java.util.StringTokenizer;
 
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
 
		int n = Integer.parseInt(r.readLine());
		// Arreglo que guarda si los vértices fueron visitados
		boolean[] visited = new boolean[n];
		int ans = 0;
		int count = 0;
 
		StringTokenizer st = new StringTokenizer(r.readLine());
		for (int i = 0; i < n; i++) {
			int num = Integer.parseInt(st.nextToken());
			if (i + 1 == num) {
				ans += 2;
			} else if (!visited[num - 1]) {
				ans++;
				visited[num - 1] = true;
			}
		}
		pw.print(ans / 2);
		pw.close();
	}
}