{"problem":{"name":"A. Petya and Catacombs","description":{"content":"A very brave explorer Petya once decided to explore Paris catacombs. Since Petya is not really experienced, his exploration is just walking through the catacombs. Catacombs consist of several rooms a","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF889A"},"statements":[{"statement_type":"Markdown","content":"A very brave explorer Petya once decided to explore Paris catacombs. Since Petya is not really experienced, his exploration is just walking through the catacombs.\n\nCatacombs consist of several rooms and bidirectional passages between some pairs of them. Some passages can connect a room to itself and since the passages are built on different depths they do not intersect each other. Every minute Petya arbitrary chooses a passage from the room he is currently in and then reaches the room on the other end of the passage in exactly one minute. When he enters a room at minute _i_, he makes a note in his logbook with number _t__i_:\n\n*   If Petya has visited this room before, he writes down the minute he was in this room last time;\n*   Otherwise, Petya writes down an arbitrary non-negative integer strictly less than current minute _i_.\n\nInitially, Petya was in one of the rooms at minute 0, he didn't write down number _t_0.\n\nAt some point during his wandering Petya got tired, threw out his logbook and went home. Vasya found his logbook and now he is curious: what is the minimum possible number of rooms in Paris catacombs according to Petya's logbook?\n\n## Input\n\nThe first line contains a single integer _n_ (1 ≤ _n_ ≤ 2·105) — then number of notes in Petya's logbook.\n\nThe second line contains _n_ non-negative integers _t_1, _t_2, ..., _t__n_ (0 ≤ _t__i_ < _i_) — notes in the logbook.\n\n## Output\n\nIn the only line print a single integer — the minimum possible number of rooms in Paris catacombs.\n\n[samples]\n\n## Note\n\nIn the first sample, sequence of rooms Petya visited could be, for example 1 → 1 → 2, 1 → 2 → 1 or 1 → 2 → 3. The minimum possible number of rooms is 2.\n\nIn the second sample, the sequence could be 1 → 2 → 3 → 1 → 2 → 1.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"一位非常勇敢的探险家彼得决定探索巴黎的地下墓穴。由于彼得经验不足，他的探索只是在墓穴中漫步。\n\n地下墓穴由若干房间和连接其中某些房间对的双向通道组成。有些通道可以连接一个房间到它自身，并且由于这些通道建造在不同深度，它们不会相互交叉。每分钟，彼得从他当前所在的房间任意选择一条通道，并在恰好一分钟内到达通道另一端的房间。当他在第 #cf_span[i] 分钟进入一个房间时，他会在他的日志本中记录一个数字 #cf_span[ti]：\n\n最初，彼得在第 #cf_span[0] 分钟时位于某个房间，他没有记录数字 #cf_span[t0]。\n\n在漫游的某个时刻，彼得感到疲惫，扔掉了日志本，回家了。瓦西里找到了他的日志本，现在他很好奇：根据彼得的日志本，巴黎地下墓穴中房间的最少可能数量是多少？\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 2·10^5]）——彼得日志本中的记录数量。\n\n第二行包含 #cf_span[n] 个非负整数 #cf_span[t1, t2, ..., tn]（#cf_span[0 ≤ ti < i]）——日志本中的记录。\n\n仅输出一行，包含一个整数——巴黎地下墓穴中房间的最少可能数量。\n\n在第一个样例中，彼得访问的房间序列可能是，例如 #cf_span[1 → 1 → 2]、#cf_span[1 → 2 → 1] 或 #cf_span[1 → 2 → 3]。房间的最少可能数量是 #cf_span[2]。\n\n在第二个样例中，序列可能是 #cf_span[1 → 2 → 3 → 1 → 2 → 1]。\n\n## Input\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 2·10^5]）——彼得日志本中的记录数量。第二行包含 #cf_span[n] 个非负整数 #cf_span[t1, t2, ..., tn]（#cf_span[0 ≤ ti < i]）——日志本中的记录。\n\n## Output\n\n仅输出一行，包含一个整数——巴黎地下墓穴中房间的最少可能数量。\n\n[samples]\n\n## Note\n\n在第一个样例中，彼得访问的房间序列可能是，例如 #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]。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"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\\} $.\n\nDefine 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).\n\nThe 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:\n\n$$\nf(i) = f(t_i) \\quad \\text{for all } i = 1, 2, \\dots, n\n$$\n\nWe 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.\n\nNote: $ 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.\n\nThus, the problem reduces to:  \n> 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 $?  \n> (Each component must be assigned a single room label; we want to minimize the total number of distinct labels.)\n\nBut 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).\n\nActually, 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).\n\nHowever, 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**.\n\nBut 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.\n\nThis is equivalent to:  \nWe 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**.\n\nBut 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.\n\nTherefore:\n\n> **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 $.**\n\nWe can compute this via union-find:\n\n- Start with $ n+1 $ components (each node separate).\n- For each $ i = 1 $ to $ n $: union $ i $ and $ t_i $.\n- The number of remaining components is the answer.\n\nBut note: we can also think greedily.\n\nAlternatively, we can simulate:\n\nLet $ \\text{comp} = n + 1 $ (initial number of components: nodes 0 to n).\n\nFor each $ i = 1 $ to $ n $:  \n if $ i $ and $ t_i $ are not yet connected, then union them and decrement $ \\text{comp} $ by 1.\n\nFinal $ \\text{comp} $ is the answer.\n\nBut we don’t need to implement union-find explicitly — we can use a DSU or just simulate with a parent array.\n\nHowever, 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.\n\nBut the cleanest formalization is:\n\n---\n\n**Formal Statement:**\n\nLet $ V = \\{0, 1, 2, \\dots, n\\} $.  \nFor each $ i \\in \\{1, 2, \\dots, n\\} $, add an undirected edge between $ i $ and $ t_i $.  \nLet $ G = (V, E) $ be the resulting undirected graph, where $ E = \\{ \\{i, t_i\\} \\mid i = 1, 2, \\dots, n \\} $.  \nThen the minimum number of rooms is the number of connected components of $ G $.\n\n---\n\n**Answer:**  \n$$\n\\boxed{\\text{number of connected components in the graph } (V, E) \\text{ as defined above}}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF889A","tags":["greedy","implementation","trees"],"sample_group":[["2\n0 0","2"],["5\n0 1 0 1 3","3"]],"created_at":"2026-03-03 11:00:39"}}