C. PolandBall and Forest

Codeforces

IDCF755C

Time1000ms

Memory256MB

Difficulty—

dfs and similardsugraphsinteractivetrees

English · Original

Chinese · Translation

Formal · Original

PolandBall lives in a forest with his family. There are some trees in the forest. Trees are undirected acyclic graphs with _k_ vertices and _k_ - 1 edges, where _k_ is some integer. Note that one vertex **is** a valid tree. There is exactly one relative living in each vertex of each tree, they have unique ids from 1 to _n_. For each Ball _i_ we know the id of its most distant relative living on the same tree. If there are several such vertices, we only know the value of the one with smallest id among those. How many trees are there in the forest? ## Input The first line contains single integer _n_ (1 ≤ _n_ ≤ 104) — the number of Balls living in the forest. The second line contains a sequence _p_1, _p_2, ..., _p__n_ of length _n_, where (1 ≤ _p__i_ ≤ _n_) holds and _p__i_ denotes the most distant from Ball _i_ relative living on the same tree. If there are several most distant relatives living on the same tree, _p__i_ is the id of one with the smallest id. It's guaranteed that the sequence _p_ corresponds to some valid forest. **Hacking**: To hack someone, you should provide a **correct forest** as a test. The sequence _p_ will be calculated according to the forest and given to the solution you try to hack as input. Use the following format: In the first line, output the integer _n_ (1 ≤ _n_ ≤ 104) — the number of Balls and the integer _m_ (0 ≤ _m_ < _n_) — the total number of edges in the forest. Then _m_ lines should follow. The _i_\-th of them should contain two integers _a__i_ and _b__i_ and represent an edge between vertices in which relatives _a__i_ and _b__i_ live. For example, the first sample is written as follows: 5 3 1 2 3 4 4 5 ## Output You should output the number of trees in the forest where PolandBall lives. [samples] ## Interaction From the technical side, this problem is interactive. However, it should not affect you (except hacking) since there is no interaction. ## Note In the first sample testcase, possible forest is: _1-2 3-4-5_. There are 2 trees overall. In the second sample testcase, the only possible graph is one vertex and no edges. Therefore, there is only one tree.

PolandBall 生活在一片森林中，与他的家人一起。森林中有一些树。树是无向无环图，包含 #cf_span[k] 个顶点和 #cf_span[k - 1] 条边，其中 #cf_span[k] 是某个整数。注意，单个顶点也是一个有效的树。每棵树的每个顶点中恰好住着一个亲属，他们的编号从 #cf_span[1] 到 #cf_span[n] 唯一。对于每个 Ball #cf_span[i]，我们知道他在同一棵树上最远的亲属的编号。如果存在多个这样的顶点，我们只知道其中编号最小的那个。问：这片森林中有多少棵树？第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 104]) —— 生活在森林中的 Ball 的数量。第二行包含一个长度为 #cf_span[n] 的序列 #cf_span[p1, p2, ..., pn]，其中 (#cf_span[1 ≤ pi ≤ n]) 成立，且 #cf_span[pi] 表示与 Ball #cf_span[i] 在同一棵树上的最远亲属的编号。如果在同一棵树上存在多个最远亲属，则 #cf_span[pi] 是其中编号最小的那个。保证序列 #cf_span[p] 对应于某个有效的森林。 *黑客攻击*：要黑客攻击某人，你需要提供一个*正确的森林*作为测试用例。序列 #cf_span[p] 将根据该森林计算得出，并作为输入提供给你要攻击的解决方案。使用以下格式：第一行输出整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 104]) —— Ball 的数量，以及整数 #cf_span[m] (#cf_span[0 ≤ m < n]) —— 森林中边的总数。接下来 #cf_span[m] 行，第 #cf_span[i] 行包含两个整数 #cf_span[ai] 和 #cf_span[bi]，表示居住在顶点 #cf_span[ai] 和 #cf_span[bi] 的亲属之间的边。例如，第一个样例应写为：你应该输出 PolandBall 所在森林中的树的数量。从技术上讲，本题是交互式的。然而，这不会影响你（除了黑客攻击），因为没有实际的交互。在第一个样例中，可能的森林是：_1-2 3-4-5_。总共有 #cf_span[2] 棵树。在第二个样例中，唯一的可能图是一个顶点且无边。因此，只有一棵树。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 104]) —— 生活在森林中的 Ball 的数量。第二行包含一个长度为 #cf_span[n] 的序列 #cf_span[p1, p2, ..., pn]，其中 (#cf_span[1 ≤ pi ≤ n]) 成立，且 #cf_span[pi] 表示与 Ball #cf_span[i] 在同一棵树上的最远亲属的编号。如果在同一棵树上存在多个最远亲属，则 #cf_span[pi] 是其中编号最小的那个。保证序列 #cf_span[p] 对应于某个有效的森林。*黑客攻击*：要黑客攻击某人，你需要提供一个*正确的森林*作为测试用例。序列 #cf_span[p] 将根据该森林计算得出，并作为输入提供给你要攻击的解决方案。使用以下格式：第一行输出整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 104]) —— Ball 的数量，以及整数 #cf_span[m] (#cf_span[0 ≤ m < n]) —— 森林中边的总数。接下来 #cf_span[m] 行，第 #cf_span[i] 行包含两个整数 #cf_span[ai] 和 #cf_span[bi]，表示居住在顶点 #cf_span[ai] 和 #cf_span[bi] 的亲属之间的边。例如，第一个样例应写为：5 31 23 44 5 ## Output 你应该输出 PolandBall 所在森林中的树的数量。 [samples] ## Interaction 从技术上讲，本题是交互式的。然而，这不会影响你（除了黑客攻击），因为没有实际的交互。 ## Note 在第一个样例中，可能的森林是：_1-2 3-4-5_。总共有 #cf_span[2] 棵树。在第二个样例中，唯一的可能图是一个顶点且无边。因此，只有一棵树。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of vertices (Balls). Let $ p = (p_1, p_2, \dots, p_n) $ be a sequence where $ p_i \in \{1, 2, \dots, n\} $ denotes the smallest-ID vertex among the most distant vertices from vertex $ i $ in the same connected component (tree). **Constraints** 1. $ 1 \leq n \leq 10^4 $ 2. $ 1 \leq p_i \leq n $ for all $ i \in \{1, \dots, n\} $ 3. The sequence $ p $ corresponds to a valid forest (undirected acyclic graph). **Objective** Determine the number of connected components (trees) in the forest.

Samples

Input #1

5
2 1 5 3 3

Output #1

Input #2

1
1

Output #2

API Response (JSON)

{
  "problem": {
    "name": "C. PolandBall and Forest",
    "description": {
      "content": "PolandBall lives in a forest with his family. There are some trees in the forest. Trees are undirected acyclic graphs with _k_ vertices and _k_ - 1 edges, where _k_ is some integer. Note that one vert",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF755C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "PolandBall lives in a forest with his family. There are some trees in the forest. Trees are undirected acyclic graphs with _k_ vertices and _k_ - 1 edges, where _k_ is some integer. Note that one vert...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "PolandBall 生活在一片森林中，与他的家人一起。森林中有一些树。树是无向无环图，包含 #cf_span[k] 个顶点和 #cf_span[k - 1] 条边，其中 #cf_span[k] 是某个整数。注意，单个顶点也是一个有效的树。\n\n每棵树的每个顶点中恰好住着一个亲属，他们的编号从 #cf_span[1] 到 #cf_span[n] 唯一。对于每个 Ball #cf_span[i]，我们...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of vertices (Balls).  \nLet $ p = (p_1, p_2, \\dots, p_n) $ be a sequence where $ p_i \\in \\{1, 2, \\dots, n\\} $ denotes the smallest-ID vertex a...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments