Overview

This problem involves a directed graph where the out-degree (number of outgoing edges) from each vertex is exactly \(1\) (Functional Graph). The task is to efficiently answer all queries asking for the “number of distinct vertices” visited starting from a specified vertex until the same vertex is visited again.

---

Analysis

Graph Structure (Functional Graph)

Since every child must pass the ball to exactly one other person, this game can be viewed as “a directed graph where every vertex has out-degree \(1\).” Such a graph is called a Functional Graph and has the following characteristics: - The graph is divided into several groups (connected components). - Each group consists of one cycle (closed loop) and trees (paths) flowing into that cycle.

Patterns in the Number of People the Ball Passes Through

When the game starts from child \(S\), the trajectory of the ball falls into one of two patterns depending on the starting position:

1. Starting point \(S\) is part of a cycle

   • The ball travels around the cycle and returns to \(S\).
   • In this case, the number of people who receive the ball equals “the length (number of vertices) of the cycle.”
   • Example: If there is a cycle of length \(3\): \(1 \to 2 \to 3 \to 1\), the answer is \(3\) regardless of where you start.

2. Starting point \(S\) is NOT part of a cycle

   • The ball travels through the tree portion outside the cycle and eventually merges into the cycle.
   • After entering the cycle, the game ends once the ball completes one full loop of the cycle starting from the merge point.
   • Therefore, the number of people who receive the ball is “the number of steps to reach the cycle + the length of the cycle joined.” In other words, if we denote the next destination as \(T_S\), this can be rephrased as \((\text{the answer when starting from child } T_S) + 1\).

Naive Approach and Its Limitations

If we simulate each query \(S_j\) individually, each query takes \(O(N)\) time in the worst case. With \(Q\) queries, the total time complexity is \(O(NQ)\), which will not fit within the time limit (TLE) under the constraints \(N, Q \le 2 \times 10^5\).

Therefore, we need the approach of “precomputing the answer for all vertices in \(O(N)\) time.”

---

Algorithm

By leveraging the structure of the graph, we precompute the answer for each vertex using the following steps:

1. Classifying Cycle and Non-Cycle (Tree) Vertices

Perform topological sort starting from vertices with in-degree (number of incoming edges) equal to \(0\). - Add vertices with in-degree \(0\) to a queue. - Remove a vertex from the queue and decrease the in-degree of its transition destination by \(1\). If any vertex newly reaches in-degree \(0\), add it to the queue. - Vertices that were visited by this operation are vertices not part of any cycle (tree portion), and vertices that were not visited are vertices that belong to a cycle.

2. Finding Cycle Lengths

For vertices belonging to cycles, detect cycles by following edges starting from unvisited vertices. - Count the number of vertices visited while traversing one full cycle, and record ans[u] = (cycle length) for all vertices \(u\) belonging to that cycle.

3. Computing Answers for Non-Cycle Vertices

Reverse the order in which vertices were processed during topological sort (topo_order). - By reversing the order, we can process vertices closer to the cycle (closer to the root of the tree) first. - When processing vertex \(u\), the answer for its transition destination \(T_u\), ans[T_u], has already been computed. - Therefore, like dynamic programming (DP), we can compute the answer in \(O(1)\) as ans[u] = ans[T_u] + 1.

4. Answering Queries

For each query \(S_j\), output the precomputed ans[S_j] in \(O(1)\).

---

Complexity

• Time Complexity: \(O(N + Q)\)

  • Topological sort, cycle detection, and reverse-order DP can all be performed in linear time \(O(N)\) with respect to the number of vertices and edges in the graph.
  • Each query is answered in \(O(1)\), so the total is \(O(N + Q)\), which comfortably fits within the time limit.

• Space Complexity: \(O(N)\)

  • Arrays for storing transitions, in-degrees, the topological sort queue, and the answer array all use \(O(N)\) memory.

---

Implementation Notes

• Using the Reverse of Topological Sort Order: Topological sort proceeds from “leaves (in-degree 0)” toward “roots (merge points with cycles).” By reversing (reverse) this order, we can explore from “roots” to “leaves,” ensuring that the information about transition destinations is always finalized when performing DP transitions.

• Fast I/O: In C++, since \(N, Q\) can be large, it is recommended to use cin.tie(NULL); ios_base::sync_with_stdio(false); to speed up input/output.

  Source Code

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, Q;
    if (!(cin >> N >> Q)) return 0;

    vector<int> T(N + 1);
    vector<int> in_degree(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        cin >> T[i];
        in_degree[T[i]]++;
    }

    // トポロジカルソートにより、サイクルに含まれない頂点を抽出する
    queue<int> que;
    for (int i = 1; i <= N; ++i) {
        if (in_degree[i] == 0) {
            que.push(i);
        }
    }

    vector<int> topo_order;
    vector<bool> is_cycle(N + 1, true);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        topo_order.push_back(u);
        is_cycle[u] = false;
        int v = T[u];
        in_degree[v]--;
        if (in_degree[v] == 0) {
            que.push(v);
        }
    }

    vector<int> ans(N + 1, 0);
    vector<bool> visited(N + 1, false);

    // サイクルに含まれる頂点について、サイクルの長さを求める
    for (int i = 1; i <= N; ++i) {
        if (is_cycle[i] && !visited[i]) {
            vector<int> cycle_nodes;
            int curr = i;
            while (!visited[curr]) {
                visited[curr] = true;
                cycle_nodes.push_back(curr);
                curr = T[curr];
            }
            int cycle_size = cycle_nodes.size();
            for (int u : cycle_nodes) {
                ans[u] = cycle_size;
            }
        }
    }

    // サイクルに含まれない頂点について、トポロジカルソートの逆順に答えを計算する
    reverse(topo_order.begin(), topo_order.end());
    for (int u : topo_order) {
        ans[u] = ans[T[u]] + 1;
    }

    // 各クエリに対する回答
    for (int q = 0; q < Q; ++q) {
        int S;
        cin >> S;
        cout << ans[S] << "\n";
    }

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.