轮舞曲roundcpp时间限制：1s 空间限制：512 MB【问题描述】n人来参加舞会编号为1~n决定跳几段轮舞曲。舞会至少有2人并且每个人正好有两个相邻的人。如果刚好有2个人参加舞会那么他们左边和右边的相邻的人相同。每个人都恰好仅认识一个人对于编号为i的人他认识的人的编号为ai你需要决定安排多少支轮舞曲满足参加舞会的每个参与者认识的那个人刚好与他相邻。例如如果有6个人他们认识的人的编号为 214

【解题思路】 首先，我们需要找出舞会的最小安排数量和最大安排数量。

最小安排数量： 我们可以通过遍历每个人的认识的人的编号，找出没有被访问过的人作为舞会的起点。 然后，我们从起点开始，沿着认识的人的编号进行轮舞，直到回到起点。 如果回到起点时，已经遍历了所有的人，则说明只需要一支轮舞曲即可满足条件。 否则，我们需要继续找出下一个没有被访问过的人作为新的起点，重复上述步骤。

最大安排数量： 我们可以将舞会的人员分成多个轮舞曲组。 我们可以通过遍历每个人的认识的人的编号，找出没有被访问过的人作为新的轮舞曲组的起点。 然后，我们从起点开始，沿着认识的人的编号进行轮舞，直到回到起点。 将这个轮舞曲组的人数加入最大安排数量中。 如果回到起点时，已经遍历了所有的人，则说明只有一个轮舞曲组。 否则，我们需要继续找出下一个没有被访问过的人作为新的轮舞曲组的起点，重复上述步骤。

【算法步骤】

1. 读入输入的人数n和每个人认识的人的编号数组a。
2. 初始化一个visited数组，用于记录每个人是否被访问过。
3. 初始化最小安排数量minCount为0，最大安排数量maxCount为0。
4. 遍历每个人的认识的人的编号：
   • 如果当前人没有被访问过，则开始寻找舞会的起点。
     • 初始化当前起点为当前人的编号。
     • 初始化当前人数count为1。
     • 将当前人标记为已访问。
     • 从当前人的认识的人的编号开始，沿着认识的人的编号进行轮舞，直到回到起点。
       • 将当前认识的人标记为已访问。
       • 将当前人数count加1。
     • 如果回到起点时，已经遍历了所有的人，则说明只需要一支轮舞曲即可满足条件，更新最小安排数量minCount为1。
     • 否则，说明需要多支轮舞曲，更新最小安排数量minCount为count。
     • 更新最大安排数量maxCount为max(maxCount, count)。
5. 输出最小安排数量minCount和最大安排数量maxCount。

【代码实现】

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<bool> visited(n + 1, false);
    int minCount = 0, maxCount = 0;

    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            int start = i;
            int count = 1;
            visited[i] = true;
            int next = a[i];
            while (next != start) {
                visited[next] = true;
                count++;
                next = a[next];
            }
            if (count == n) {
                minCount = 1;
            } else {
                minCount = count;
            }
            maxCount = max(maxCount, count);
        }
    }

    cout << minCount << " " << maxCount << endl;

    return 0;
}
``