En este problema, se consideran n estudiantes en un aula. Cada estudiante (excluyendo al monitor principal, asignado con identificador 0) supervisa a otro estudiante específico. El objetivo es seleccionar el mayor número posible de estudiantes para una tarea, garantizando que para cada estudiante seleccionado, al menos uno de sus supervisores directos no sea seleccionado. Si un estudiante no es supervisado por ningún otro, no puede ser elegido.

Formato de entrada

La primera línea contiene un entero n, que representa la cantidad de estudiantes (numerados del 1 al n). Las siguientes n líneas contienen cada una un entero a_k, donde a_k indica que el estudiante k supervisa al estudiante a_k. Se cumple que 1 ≤ a_k ≤ n y a_k ≠ k.

Formato de salida

Imprimir un solo entero: el número máximo de estudiantes que pueden ser seleccionados.

Ejemplo

Entrada:

6
2
3
1
3
6
5

Salida:

3

Enfoque de solución

El problema se modela como un grafo dirigido donde cada nodo tiene exactamente un arco saliente. La solución utiliza un enfoque voraz y procesamiento en lotes para manejar los componentes conexos, que pueden ser árboles o ciclos con ramas. Primero, se identifican nodos sin entradas (grado cero), ya que no pueden ser seleccionados. Luego, se propagan decisiones: si un nodo no se selecciona, su hijo debe selecccionarse, y viceversa, respetando las restricciones. Para los ciclos restantes, se toman decisiones locales para maximizar la selección.

Implementación en C++

A continuación se muestra el código resuelto, con variables renombradas y estructura ligeramente adaptada para claridad:

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 5;
int n, objetivo[MAX_N], grado[MAX_N], respuesta;
int estado[MAX_N]; // -1: no seleccionado, 0: sin decidir, 1: seleccionado
queue<int> cola;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int idx = 1; idx <= n; ++idx) {
        cin >> objetivo[idx];
        ++grado[objetivo[idx]];
    }
    for (int idx = 1; idx <= n; ++idx) {
        if (grado[idx] == 0) {
            cola.push(idx);
            estado[idx] = -1;
        }
    }
    while (!cola.empty()) {
        int nodo_actual = cola.front();
        cola.pop();
        --grado[objetivo[nodo_actual]];
        if (estado[nodo_actual] == -1) {
            if (estado[objetivo[nodo_actual]] == 0)
                cola.push(objetivo[nodo_actual]);
            estado[objetivo[nodo_actual]] = 1;
        } else if (grado[objetivo[nodo_actual]] == 0 && estado[objetivo[nodo_actual]] == 0) {
            cola.push(objetivo[nodo_actual]);
            estado[objetivo[nodo_actual]] = -1;
        }
    }
    for (int idx = 1; idx <= n; ++idx) {
        if (estado[idx] == 0) {
            estado[idx] = -1;
            int recorrido = idx;
            while (estado[objetivo[recorrido]] == 0) {
                if (estado[recorrido] == 1)
                    estado[objetivo[recorrido]] = -1;
                else
                    estado[objetivo[recorrido]] = 1;
                recorrido = objetivo[recorrido];
            }
        }
    }
    for (int idx = 1; idx <= n; ++idx)
        if (estado[idx] == 1)
            ++respuesta;
    cout << respuesta;
    return 0;
}

El código utiliza una cola para procesar nodos con grado cero y propaga las decisionse a lo largo de las cadenas. Luego, maneja los ciclos independientes aseguranod consistencia en las asignaciones de estado. La complejidad temporal es lineal, adecuada para restricciones grandes.