CSES - Planets Cycles

Define the number of teleportations starting from a planet as the $\texttt{pathlength}$ of that planet. For each planet that hasn't been visited, we want to find its $\texttt{pathlength}$. Call the planet we are performing $\texttt{dfs}$ from the $\textit{start}$. As we perform $\texttt{dfs}$ from the $\textit{start}$, keep track of the planets seen, in order, in the $\texttt{path}$ queue and keep track of $\texttt{steps}$, the length of the path (which is also the $\texttt{pathlength}$ of the $\textit{start}$). When we reach a planet that has already been visited (call this planet the $\textit{repeat}$), add the $\texttt{pathlength}$ of the $\textit{repeat}$ to the current $\texttt{step}$ count because we would continue to visit all of the planets that $\textit{repeat}$ would go on to visit.

Once we have $\texttt{path}$ and $\texttt{steps}$ we can calculate the $\texttt{pathlength}$ of all the planets in this $\texttt{path}$. We know the $\textit{repeat}$ will always be the planet at the end of the $\texttt{path}$, but it may appear elsewhere as well. We can break this down into two cases:

1. The $\textit{repeat}$ was visited twice in the current $\texttt{path}$. The planets in the $\texttt{path}$ between the two occurrences of the $\textit{repeat}$ form a $\textit{cycle}$.
2. The $\textit{repeat}$ only appears at the end of the current $\texttt{path}$. All of the planets in the $\texttt{path}$ are not part of a $\textit{cycle}$.

For planets inside a $\textit{cycle}$, the repeating planet when starting from that planet is itself. For all the planets in the $\texttt{path}$ but outside the $\textit{cycle}$, the planet that repeats when starting from each planet will still be the $\textit{repeat}$.

Since the planets outside the $\textit{cycle}$ all have paths ending at the $\textit{repeat}$, each one's $\texttt{pathlength}$ is $1$ less than the previous'. So, as we iterate through the planets along the $\texttt{path}$ that are outside the $\textit{cycle}$, the $\texttt{pathlength}$ will decrease by $1$ each time, starting from the $\textit{start}$ with a $\texttt{pathlength}$ of $\texttt{steps}$. Once we get to the $\textit{cycle}$, the $\texttt{pathlength}$ of the planets will all be equal to the $\texttt{pathlength}$ of the $\textit{repeat}$, which is the length of the $\textit{cycle}$.

Copy
#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;

Copy
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();

Copy
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.