A. Petya and Catacombs

一位非常勇敢的探险家彼得决定探索巴黎的地下墓穴。由于彼得经验不足，他的探索只是在墓穴中漫步。 地下墓穴由若干房间和连接其中某些房间对的双向通道组成。有些通道可以连接一个房间到它自身，并且由于这些通道建造在不同深度，它们不会相互交叉。每分钟，彼得从他当前所在的房间任意选择一条通道，并在恰好一分钟内到达通道另一端的房间。当他在第 #cf_span[i] 分钟进入一个房间时，他会在他的日志本中记录一个数字 #cf_span[ti]： 最初，彼得在第 #cf_span[0] 分钟时位于某个房间，他没有记录数字 #cf_span[t0]。 在漫游的某个时刻，彼得感到疲惫，扔掉了日志本，回家了。瓦西里找到了他的日志本，现在他很好奇：根据彼得的日志本，巴黎地下墓穴中房间的最少可能数量是多少？ 第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 2·10^5]）——彼得日志本中的记录数量。 第二行包含 #cf_span[n] 个非负整数 #cf_span[t1, t2, ..., tn]（#cf_span[0 ≤ ti < i]）——日志本中的记录。 仅输出一行，包含一个整数——巴黎地下墓穴中房间的最少可能数量。 在第一个样例中，彼得访问的房间序列可能是，例如 #cf_span[1 → 1 → 2]、#cf_span[1 → 2 → 1] 或 #cf_span[1 → 2 → 3]。房间的最少可能数量是 #cf_span[2]。 在第二个样例中，序列可能是 #cf_span[1 → 2 → 3 → 1 → 2 → 1]。 ## Input 第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 2·10^5]）——彼得日志本中的记录数量。第二行包含 #cf_span[n] 个非负整数 #cf_span[t1, t2, ..., tn]（#cf_span[0 ≤ ti < i]）——日志本中的记录。 ## Output 仅输出一行，包含一个整数——巴黎地下墓穴中房间的最少可能数量。 [samples] ## Note 在第一个样例中，彼得访问的房间序列可能是，例如 #cf_span[1 → 1 → 2]、#cf_span[1 → 2 → 1] 或 #cf_span[1 → 2 → 3]。房间的最少可能数量是 #cf_span[2]。在第二个样例中，序列可能是 #cf_span[1 → 2 → 3 → 1 → 2 → 1]。

Let $ n $ be the number of log entries, and let $ t_1, t_2, \dots, t_n $ be the sequence of timestamps recorded at each step, where $ 0 \leq t_i < i $ for each $ i \in \{1, 2, \dots, n\} $. Define a function $ f: \{1, 2, \dots, n\} \to \mathbb{N} $, where $ f(i) $ is the room number visited at minute $ i $, and $ f(0) $ is the initial room (unknown, not recorded). The logbook records: at minute $ i $, Petya entered a room and noted the time $ t_i $, meaning that the room visited at minute $ i $ was **also** visited at minute $ t_i $. That is: $$ f(i) = f(t_i) \quad \text{for all } i = 1, 2, \dots, n $$ We are to find the **minimum** number of distinct rooms (i.e., distinct values in the set $ \{f(0), f(1), \dots, f(n)\} $) consistent with these constraints. Note: $ f(0) $ is not constrained by any $ t_i $, but all $ f(i) $ for $ i \geq 1 $ are forced to equal $ f(t_i) $, and $ t_i < i $, so the constraints form a directed acyclic graph (DAG) over indices $ 0 $ to $ n $, with edges $ i \to t_i $ for $ i \geq 1 $, and $ f $ must be constant on connected components of this DAG. Thus, the problem reduces to: > How many distinct connected components are there in the directed graph with nodes $ \{0, 1, \dots, n\} $, and edges $ i \to t_i $ for $ i = 1, \dots, n $? > (Each component must be assigned a single room label; we want to minimize the total number of distinct labels.) But note: since each $ i \geq 1 $ has exactly one outgoing edge to $ t_i $, and $ t_i < i $, the structure is a **forest of trees** rooted at nodes with no incoming constraints (i.e., nodes that are never pointed to by any $ t_j $, except possibly 0). Actually, since each node $ i \geq 1 $ points to some $ t_i < i $, the entire structure is a **forest of trees** with roots in $ \{0\} \cup \{ \text{nodes not pointed to by any } t_i \} $. But 0 is always a root (since $ t_i < i $, and $ t_i \geq 0 $, so no $ t_i = 0 $ forces a constraint on 0 — 0 is the starting point). However, the key insight is: **each connected component (under the undirected version of the constraint graph) must be assigned one room**. But since the graph is directed from higher index to lower, and we are enforcing $ f(i) = f(t_i) $, then **all nodes in the same connected component (via the undirected version of the constraint graph) must have the same room label**. But actually, because the constraint is $ f(i) = f(t_i) $, and $ t_i < i $, we can process nodes in increasing order and union the equivalence classes. This is equivalent to: We start with room labels assigned arbitrarily. We are forced to assign the same room to $ i $ and $ t_i $. So we can model this as a **union-find** (disjoint set union) problem over indices $ 0 $ to $ n $, where for each $ i = 1 $ to $ n $, we union $ i $ and $ t_i $. The number of distinct connected components after all unions is the **minimum number of rooms**. But note: we are not forced to assign different rooms to different components — we want the *minimum* number of rooms, so we assign one room per connected component. Therefore: > **Minimum number of rooms = number of connected components in the undirected graph on vertices $ \{0, 1, \dots, n\} $, with edges $ \{i, t_i\} $ for $ i = 1 $ to $ n $.** We can compute this via union-find: - Start with $ n+1 $ components (each node separate). - For each $ i = 1 $ to $ n $: union $ i $ and $ t_i $. - The number of remaining components is the answer. But note: we can also think greedily. Alternatively, we can simulate: Let $ \text{comp} = n + 1 $ (initial number of components: nodes 0 to n). For each $ i = 1 $ to $ n $:  if $ i $ and $ t_i $ are not yet connected, then union them and decrement $ \text{comp} $ by 1. Final $ \text{comp} $ is the answer. But we don’t need to implement union-find explicitly — we can use a DSU or just simulate with a parent array. However, note that $ t_i < i $, so when we process $ i $, $ t_i $ has already been processed (or is 0), so we can track the component representative of each node as we go. But the cleanest formalization is: --- **Formal Statement:** Let $ V = \{0, 1, 2, \dots, n\} $. For each $ i \in \{1, 2, \dots, n\} $, add an undirected edge between $ i $ and $ t_i $. Let $ G = (V, E) $ be the resulting undirected graph, where $ E = \{ \{i, t_i\} \mid i = 1, 2, \dots, n \} $. Then the minimum number of rooms is the number of connected components of $ G $. --- **Answer:** $$ \boxed{\text{number of connected components in the graph } (V, E) \text{ as defined above}} $$