轮舞曲（round.cpp） - 最少和最多轮舞曲数量求解

问题描述

n人来参加舞会，编号为1~n，决定跳几段轮舞曲。舞会至少有2人，并且每个人正好有两个相邻的人。如果刚好有2个人参加舞会，那么他们左边和右边的相邻的人相同。每个人都恰好仅认识一个人，对于编号为i的人，他认识的人的编号为ai 你需要决定安排多少支轮舞曲，满足参加舞会的每个参与者认识的那个人刚好与他相邻。

例如，如果有6个人，他们认识的人的编号为 '2,1,4,3,6,5' 则轮舞曲的最少数量为 1： ·1−2−3−4−5−6−1 最大为 3： ·1−2−1 ·3−4−3 ·5−6−5

输入格式

第一行一个整数n，表示参与舞会的人数。第二行n个整数a1,a2,…,an，第i个数表示编号为i的人仅认识的那个人的编号为ai。保证输入的数据合法。

输出格式

一行两个整数，第一个为安排轮舞曲数量的最小值，第二个为安排轮舞曲数量的最大值。

输入样例

9
2 3 2 5 6 5 8 9 8

输出样例

1 3

样例解释

最小数量的安排方式： ·1-2-3-4-5-6-7-8-9 最大数量的安排方式： ·1-2-3 ·4-5-6 ·7-8-9

数据范围及约定

对于40%的数据，1≤n≤6 对于另外40%的数据，1≤n≤100，且满足a数组为长度为n的排列对于100%的数据，1≤n≤2×105，1≤ai≤n，且ai≠i

解题思路

首先，我们需要找出舞会的最小安排数量和最大安排数量。

最小安排数量

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

最大安排数量

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

算法步骤

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