Overview

This is a problem where you need to find the number of stations visited when traveling from Station 1 to Station N by transferring between trains, where each station has a fixed next station to move to.

Analysis

In this problem, the structure is simple: from each station \(i\), you always move to station \(P_i\). The route from Station 1 to Station N is uniquely determined by this movement rule. In other words, we can find the route by repeatedly following: Station 1 → Station \(P_1\) → Station \(P_{P_1}\) → …, continuing until we reach Station N.

A straightforward approach is to actually simulate the movement from Station 1 to Station N while recording the intermediate stations. Although the input size can be as large as 200,000 stations, since each station has exactly one destination, we can solve this efficiently by simply simulating the movement.

Algorithm

1. Initialize the current position as Station 1
2. Repeat the following until the current position is Station N:
   • Add the current position to the route
   • Move to the next station (\(P_{current-1}\)) from the current position
3. When Station N is reached, add Station N to the route as well
4. Output the length of the route list

This algorithm accurately counts the number of stations visited by actually tracing the route from Station 1 to Station N. Since the problem constraints guarantee that Station N is always reachable from Station 1, there is no risk of an infinite loop.

Complexity

• Time complexity: \(O(K)\) (where K is the number of stations visited from Station 1 to Station N)
• Space complexity: \(O(K)\) (for the list storing the route)

Since the route may contain up to N stations, the worst case uses \(O(N)\) memory, but this is well within the constraints.

Implementation Notes

• Be careful with array indexing: the information for station \(i\) is stored at index \(i-1\) in the array

• Terminate the loop when Station N is reached

• Don’t forget to add Station N itself to the route at the end

• Note that since there is no information for Station N, only \(N-1\) data values are given in the input

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    P = list(map(int, data[1:1+n-1]))
    
    path = []
    current = 1
    while current != n:
        path.append(current)
        current = P[current-1]
    path.append(n)
    
    print(len(path))

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.