Skip to Content
CTRL K

Medium Demon Problem (easy version)

Editorial oficial (C++) 

Explicación

Primero, observemos la estructura del grafo. Cada nodo tiene exactamente una arista saliente, así que es un grafo funcional (functional graph). Por lo tanto, el grafo consiste en varias componentes conexas, cada una con exactamente un ciclo, y todos los nodos están en el ciclo o eventualmente desembocan en él. La distribución final resultante consistirá en que cada nodo del ciclo tiene 11 peluche y todos los demás tienen 00.

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. En algún año, las arañas pasarán su peluche (si tienen uno) a rir_i. Sin embargo, cada año algunas de las arañas que envían un peluche ya no recibirán uno a cambio, y el sistema cambia de cantidades. Una vez que todos los peluches llegan a un ciclo, cada araña recibe y da un peluche, y el sistema se mantiene estable.

Por lo tanto, el problema se reduce a hallar la distancia máxima de cualquier nodo a su ciclo respectivo, que es el tiempo máximo que tardan todos los peluches en llegar a 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> count(n);
	vector<bool> visited(n);
	int ans = 2;
 
	// DFS que sale del nodo para hallar la longitud máxima de camino
	auto dfs = [&](auto &&self, int node) -> int {
		int mx = 0;
		visited[node] = true;
		for (int next_node : adj[node]) {
			if (count[next_node] != 2) { mx = max(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 de un ciclo
			while (count[node] != 2) {
				visited[node] = true;
				count[node]++;
				if (count[node] == 2) nodes.push_back(node);
				node = a[node];
			}
 
			// DFS sobre los nodos del ciclo para obtener la longitud
			// máxima de camino hacia nodes[i]
			for (int j = 0; j < nodes.size(); j++) {
				int d = dfs(dfs, nodes[j]);
				ans = max(d + 1, ans);
			}
		}
	}
 
	cout << ans << '\n';
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int t;
	cin >> t;
	while (t--) { solve(); }
}
Fundamentos