Planets Cycles

Explicación

Definamos el número de teletransportaciones partiendo de un planeta como el $\texttt{pathlength}$ de ese planeta. Para cada planeta que no ha sido visitado, queremos hallar su $\texttt{pathlength}$ . Llamemos $\textit{start}$ al planeta desde el que ejecutamos $\texttt{dfs}$ . Al ejecutar $\texttt{dfs}$ desde el $\textit{start}$ , llevamos cuenta de los planetas vistos, en orden, en la cola $\texttt{path}$ y llevamos cuenta de $\texttt{steps}$ , la longitud del camino (que también es el $\texttt{pathlength}$ del $\textit{start}$ ). Cuando llegamos a un planeta que ya fue visitado (llamemos a este planeta el $\textit{repeat}$ ), sumamos el $\texttt{pathlength}$ del $\textit{repeat}$ al conteo actual de $\texttt{step}$ porque continuaríamos visitando todos los planetas que el $\textit{repeat}$ iría a visitar.

Una vez que tenemos $\texttt{path}$ y $\texttt{steps}$ podemos calcular el $\texttt{pathlength}$ de todos los planetas de este $\texttt{path}$ . Sabemos que el $\textit{repeat}$ siempre será el planeta al final del $\texttt{path}$ , pero también puede aparecer en otro lugar. Podemos dividirlo en dos casos:

El $\textit{repeat}$ se visitó dos veces en el $\texttt{path}$ actual. Los planetas del $\texttt{path}$ entre las dos ocurrencias del $\textit{repeat}$ forman un $\textit{cycle}$ .
El $\textit{repeat}$ solo aparece al final del $\texttt{path}$ actual. Todos los planetas del $\texttt{path}$ no forman parte de un $\textit{cycle}$ .

Para los planetas dentro de un $\textit{cycle}$ , el planeta que se repite al partir de ese planeta es él mismo. Para todos los planetas del $\texttt{path}$ pero fuera del $\textit{cycle}$ , el planeta que se repite al partir de cada planeta seguirá siendo el $\textit{repeat}$ .

Como los planetas fuera del $\textit{cycle}$ tienen todos caminos que terminan en el $\textit{repeat}$ , el $\texttt{pathlength}$ de cada uno es $1$ menos que el anterior. Así, al iterar por los planetas a lo largo del $\texttt{path}$ que están fuera del $\textit{cycle}$ , el $\texttt{pathlength}$ disminuirá en $1$ cada vez, partiendo del $\textit{start}$ con un $\texttt{pathlength}$ de $\texttt{steps}$ . Una vez que llegamos al $\textit{cycle}$ , el $\texttt{pathlength}$ de los planetas será igual al $\texttt{pathlength}$ del $\textit{repeat}$ , que es la longitud del $\textit{cycle}$ .

Implementación

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

C++JavaPython


#include <iostream>
#include <queue>
using namespace std;
void dfs(int planet);
 
bool visited[200000]{};
int destinations[200000];
int pathlength[200000]{};
queue<int> path;
int steps = 0;
 
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> destinations[i];
		destinations[i]--;
	}
	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			steps = 0;
			dfs(i);
			int decrement = 1;
			// for each planet in current path, calculate pathlength
			while (!path.empty()) {
				// we are in the cycle; all nodes have same pathlength
				if (path.front() == path.back()) { decrement = 0; }
				pathlength[path.front()] = steps;
				steps -= decrement;
				path.pop();
			}
		}
	}
	for (int i = 0; i < n; i++) { cout << pathlength[i] << " "; }
	cout << endl;
	return 0;
}
 
void dfs(int planet) {
	// add planet to path
	path.push(planet);
	if (visited[planet]) {
		// add pathlength of the repeat planet to current step count
		steps += pathlength[planet];
		return;
	}
	visited[planet] = true;
	steps++;
	dfs(destinations[planet]);
}


import java.io.*;
import java.util.*;
 
public class PlanetCycles {
	static int N, steps;
	static int[] destinations, pathlength;
	static boolean[] visited;
	static LinkedList<Integer> path = new LinkedList<>();
	public static void main(String[] args) {
		Kattio io = new Kattio();
		N = io.nextInt();
		destinations = new int[N + 1];
		visited = new boolean[N + 1];
		pathlength = new int[N + 1];
		for (int i = 1; i < N + 1; i++) { destinations[i] = io.nextInt(); }
 
		for (int i = 1; i < N + 1; i++) {
			if (!visited[i]) {
				steps = 0;
				dfs(i);
				int decrement = 1;
				Integer last = path.peekLast();
				while (!path.isEmpty()) {
					if (path.peekFirst().equals(last)) decrement = 0;
					pathlength[path.poll()] = steps;
					steps -= decrement;
				}
			}
		}
 
		for (int i = 1; i < N + 1; i++) { io.print(pathlength[i] + " "); }
		io.close();
	}
 
	public static void dfs(int n) {
		visited[n] = true;
		path.add(n);
		steps++;
		if (!visited[destinations[n]]) dfs(destinations[n]);
		else {
			path.add(destinations[n]);
			steps += pathlength[destinations[n]];
		}
	}
 
	// CodeSnip{Kattio}
}


n = int(input())
planets = list(map(lambda i: int(i) - 1, input().split()))
 
path_length = [0] * n
visited = [False] * n
 
for i in range(len(planets)):
	"""
	We dfs from the current planet until we end up at a planet we have already
	visited. Note that the visited planet is not added to the path array.
	"""
 
	if visited[i]:
		continue
 
	path = [i]  # The path of planets whose teleporters we go through
	path_set = set([i])  # Set of all planets whose teleporters we go through
	visited[i] = True
	while not visited[planets[i]]:
		i = planets[i]
		visited[i] = True
		path.append(i)
		path_set.add(i)
 
	"""
	Let i be the planet we have already visited. If i exists in path, then
	there is a cycle. When there is a cycle, all planets in that cycle have the
	same path length (the distance for each planet to visit itself).
	"""
	i = planets[i]
	if i in path_set:
		# If there is a cycle, the planets in [i, ..., i) are in the cycle.
		# This is every element from the end of path until we hit i.
		path_cycle = [path.pop()]  # The path of planets in the cycle.
		while path_cycle[-1] != i:
			path_cycle.append(path.pop())
 
		for planet in path_cycle:
			path_length[planet] = len(path_cycle)
 
	"""
	For planets outside the cycle (or if there is none), the path length of
	a planet is the path length of the planet the former planet's teleporter
	can visit, plus one.
	"""
	while path:
		top = path.pop()
		path_length[top] = path_length[planets[top]] + 1
 
print(*path_length)