Intermediate.
Put your skills to the test.

Problem summary

Start at teleport 0 and repeatedly follow its single outgoing destination. Count teleports visited only once, teleports repeated forever, and teleports never reached.

Constraints

The source specifies fewer than 10000 teleports; every destination is a valid index.

Worked example

Input and output for the worked example discussed below.

10
8 0 7 6 1 6 2 9 3 6

3 4 3

Solution analysis

1. An outgoing destination is fixed, so the walk is deterministic. Once a previously visited vertex is reached, the entire future repeats the same directed cycle.
2. Store the step number of the first visit to each teleport, initially −1. Follow destinations while the current vertex has no first-visit number. If the walk has visited steps vertices and repeats vertex v, the tail has first[v] vertices and the cycle has steps−first[v].
3. The sample walk begins 0,8,3,6,2,7,9 and repeats 6. First[6]=3 and steps=7, giving tail 3, cycle 4, and 10−7=3 unreachable vertices. Only the walk from 0 matters; other cycles elsewhere remain unreachable.

Why it works

Before repetition every visited vertex is distinct. The segment before the repeated vertex is never revisited, while the segment from its first visit to repetition forms a closed deterministic cycle repeated indefinitely. All vertices absent from that prefix-plus-cycle walk are unreachable.

Watch out. Teleports use zero-based labels in this original problem. Start at 0, not at an arbitrary unvisited vertex, and distinguish the tail from the eventual cycle.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int>next(n);
    vector<int>first(n,-1);
    for(int&destination:next){
        cin>>destination;
    }
    int current=0;
    int steps=0;
    while(first[current]==-1){
        // The first-visit index locates the eventual cycle's beginning.
        first[current]=steps;
        steps++;
        current=next[current];
    }
    cout<<first[current]<<' '<<steps-first[current]<<' '<<n-steps<<'\n';
}