花车巡游

题目描述

嘉年华的花车巡游正在展示精心编排的队列变换！

最初，所有 N辆花车排成一行，花车 i 位于第 i 位。变换程序由 K 个位置对 (a₁,b₁),(a₂,b₂),…,(a_K,b_K) 描述。表演过程中：

· 第 1 分钟：位置 a₁ 与 b₁ 的花车交换位置

· 第 2 分钟：位置 a₂ 与 b₂ 的花车交换位置

· ……

· 第 K 分钟：位置 a_K 与 b_K 的花车交换位置

· 第 K+1 分钟：重新从 (a₁,b₁) 开始交换（即位置 a₁ 与 b₁ 交换）

· 第 K+2 分钟：位置 a₂ 与 b₂ 交换

· 如此无限循环……

请计算每辆花车在整个表演过程中能到达的不同位置数量。

输入格式

第一行输入 N,K。

接下来 K 行每行包含 a_i,b_i（1≤a_i<b_i≤N）。

输出格式

输出 N行，第 i行为花车 i能到达的不同位置数量。

输入样例

5 4
1 3
1 2
2 3
2 4

输出样例

4
4
3
4
1

说明提示

样例解释

· 花车 1 可到达位置 {1,2,3,4}

· 花车 2 可到达位置 {1,2,3,4}

· 花车 3 可到达位置 {1,2,3}

· 花车 4 可到达位置 {1,2,3,4}

· 花车 5 始终在位置 5（未移动）

【数据范围】

1≤K≤2×10⁵

2≤N≤10⁵

限制

时间限制：1000ms

内存限制：256MiB

此题需要使用循环和数组来解决。首先，我们需要统计每辆花车在整个表演过程中能到达的不同位置数量。我们可以使用一个数组来记录每辆花车的位置变化。对于每对交换的位置对 (a, b)，我们可以将花车 a 的位置添加到花车 b 的位置变化的集合中，同时将花车 b 的位置添加到花车 a 的位置变化的集合中。这样，我们就可以计算出每辆花车在整个表演过程中能到达的不同位置数量。最后，对于每辆花车，输出其能到达的不同位置数量即可。

为了解决这个问题，我们可以按照以下步骤进行：

1. 读取输入数据：N 和 K。
2. 初始化一个大小为 N 的数组 pos，用于记录每辆花车的初始位置。初始时，pos[i] = i。
3. 对于每一对交换的位置对 (a, b)，执行以下操作：
   a. 将 pos[a] 添加到 pos[b] 的位置变化的集合中（使用一个集合或数组来记录）。
   b. 将 pos[b] 添加到 pos[a] 的位置变化的集合中。
4. 对于每辆花车 i，统计其能到达的不同位置数量。可以通过遍历其位置变化的集合来实现。对于每个位置 j 在集合中出现的次数，如果次数为偶数，说明花车 i 可以到达位置 j；如果次数为奇数，则说明不能到达。因此，我们可以统计每个位置被访问的奇数次数的数量，并累加到结果中。
5. 输出每辆花车能到达的不同位置数量。

下面是具体的 C 语言代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXN 100010
int N, K;
int pos[MAXN]; // 记录每辆花车的初始位置
bool vis[MAXN]; // 记录每个位置是否被访问过
int main() {
    scanf("%d%d", &N, &K);
    for (int i = 1; i <= N; i++) {
        pos[i] = i; // 初始化每辆花车的初始位置
    }
    for (int i = 0; i < K; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        // 将 a 的位置添加到 b 的访问集合中，将 b 的位置添加到 a 的访问集合中
        vis[pos[a]] = true;
        vis[pos[b]] = true;
        // 交换位置
        int temp = pos[a];
        pos[a] = pos[b];
        pos[b] = temp;
    }
    for (int i = 1; i <= N; i++) {
        int count = 0; // 统计奇数次访问的位置数量
        for (int j = 1; j <= N; j++) {
            if (vis[j] && j != i && ((j - i) % 2 == 1)) { // 判断位置是否被奇数次访问且不等于当前花车的初始位置
                count++; // 统计奇数次访问的位置数量加一
            }
        }
        printf("%d\n", count + 1); // 输出结果（加一并输出）
    }
    return 0;
}