Problem Info
I used the same solution as USACO guide for the Planet Cyles problem. However, it times out on 1 test case. Can someone please have a look for me and tell me why it is timing out? Is it because I am using Java?
My Work
import java.io.*;
import java.util.*;
class cses {
static int n;
static boolean[] used;
static LinkedList<Integer> cycle = new LinkedList<>();
static int steps;
static int[] arr;
static int[] ans;
public static void main(String[] args) throws IOException{
BufferedReader file = new BufferedReader(new InputStreamReader(System.in));
//BufferedReader file = new BufferedReader(new FileReader("paint.in"));
StringTokenizer st = new StringTokenizer(file.readLine());
n = Integer.parseInt(st.nextToken());
arr = new int[n];
st = new StringTokenizer(file.readLine());
for (int i=0; i<n; i++){
arr[i] = Integer.parseInt(st.nextToken())-1;
}
ans = new int[n];
used = new boolean[n];
for (int i=0; i<n; i++){
if (!used[i]){
steps = 0;
dfs(i);
int decrease = 1;
int last = cycle.peekLast();
while (!cycle.isEmpty()){
if (cycle.peekFirst().equals(last)){
decrease = 0; // no need to decrease
}
int index = cycle.poll();
ans[index] = steps;
steps -= decrease;
}
}
}
for (int i : ans){
System.out.print(i + " ");
}
}
public static void dfs(int curr){
used[curr] = true;
cycle.add(curr);
steps++;
int next = arr[curr];
if (!used[next]){
dfs(next);
}else{
cycle.add(next);
steps += ans[next];
}
}
}
Thinking
The thinking is just trying to find all the cycles, and all elements within the cycle should have the same answer for how many travels before returning to a “used” planet. For a node that connects to a cycle but isn’t in the cycle itself, the answer will be greater than those connected in the cycle. We will process those not in the cycle first and decrease the “steps” variable, and eventually, we will reach nodes that are in the cycle and we don’t need to decrease anymore.
My question
I think the program will only pass through every node once because it will return once it sees a used node. Therefore, I am don’t understanding why it is timing out?