Skip to Content
CTRL K

Medium Demon Problem (hard version)

Editorial oficial (C++) 

Explicación

Primero, observemos la estructura del grafo. Cada nodo tiene una única arista saliente, así que es un grafo funcional (functional graph). En consecuencia, el grafo consiste en varias componentes conexas, cada una con exactamente un ciclo, y todos los nodos están en el ciclo o desembocan en él.

Nótese que, si un nodo no está en el ciclo, el proceso no se estabiliza hasta que el peluche de ese nodo llega al ciclo. Consideremos los nodos a lo largo de un camino que entra a un ciclo. Cada día, las arañas pasan uno de sus peluches (si tienen alguno) a rir_i. Sin embargo, algunas de las arañas que envían un peluche no recibirán uno a cambio, y el sistema cambia de cantidades. Así, como en la versión fácil, una vez que todos los peluches llegan a un ciclo, cada araña recibe y da un peluche, y el sistema se mantiene estable.

A diferencia de la versión fácil, las arañas ahora pueden tener varios peluches. Modelamos cada componente conexa como un ciclo con árboles enraizados pegados a sus nodos, donde cada árbol está enraizado en un nodo del ciclo. Entonces, ¿cuánto tarda una araña ii de un árbol en entregar todos sus peluches? Eso es igual al tamaño del subárbol de ii, porque la araña ii entrega exactamente un peluche por año, y todos los peluches del subárbol de ii deben pasar por ii.

Además, podemos pensar el tiempo a través de dos factores acotantes. El tiempo que tardarían todos los peluches en fluir hacia un ciclo por la entrada ii, y el tiempo máximo que tardaría un peluche en llegar al ciclo (profundidad máxima). Como el tamaño del subárbol es siempre mayor o igual que la profundidad máxima, basta tomar el máximo tamaño de subárbol como respuesta.

Construyendo una lista de adyacencia aparte, podemos ejecutar un DFS en cada uno de estos árboles y calcular todos los tamaños de subárbol, ignorando la raíz (que forma parte del ciclo). La respuesta final será el máximo tamaño de subárbol entre todos esos nodos, porque ese es el tiempo máximo que tardan todos los peluches en fluir hacia los ciclos.

Implementación

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

 
#include <bits/stdc++.h>
using namespace std;
 
void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	vector<vector<int>> adj(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		a[i]--;
		adj[a[i]].push_back(i);
	}
 
	vector<int> counts(n);
	vector<bool> visited(n);
	int ans = 2;
 
	// DFS que recorre los árboles y devuelve tamaños de subárbol
	auto dfs = [&](auto &&self, int node) -> int {
		int mx = 0;
		visited[node] = true;
		for (int next_node : adj[node]) {
			if (counts[next_node] != 2) { mx += self(self, next_node); }
		}
		return mx + 1;
	};
 
	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			int node = i;
			vector<int> nodes;
 
			// Obtenemos todos los nodos del ciclo
			while (counts[node] != 2) {
				visited[node] = true;
				counts[node]++;
				if (counts[node] == 2) nodes.push_back(node);
				node = a[node];
			}
 
			// DFS en cada árbol enraizado en el ciclo
			int cur = 0;
			for (int j = 0; j < nodes.size(); j++) {
				for (int root : adj[nodes[j]]) {
					if (counts[root] != 2) {
						int subtree_size = dfs(dfs, root);
						cur = max(subtree_size + 2, cur);
					}
				}
			}
			ans = max(ans, cur);
		}
	}
	cout << ans << '\n';
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	cin >> t;
	while (t--) { solve(); }
}
Fundamentos