Dance Mooves (USACO Silver 2021 January)

$10^5$ 头牛，给定 $K$ 个不断重复的两头牛置换序列（ $K \leq 2\cdot 10^5$ ），求每头牛一共可以到达多少个位置。

更换位置的题目，总体上是置换和排列的问题，往往涉及到全排列分解为环（置换的轮换表示）。比如：

\sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 6 & 5 & 4 & 3 & 1 \end{pmatrix} = (126)(35)(4)=(126)(35)

在此题中，把K个交换动作都做一遍，可以得到整个周期的置换P，根据以上基础知识，P一定是由若干个轮换（Cycle）组成的。这时我们可以看到对于同一个轮换上的所有牛，他们能到达的位置都是一样的。所以我们可以把所有同一个轮换上的牛同样对待，用轮换的编号来代替他们，每个置换维护一个可到达的位置集合，然后对所有交换动作模拟一遍，就完成了所有轮换分别可到达的位置集合的统计。

📙 Dance Mooves讲解幻灯片

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, k;
pair<int,int> ops[200005];
int p[100005];  // 置换P
int c[100005];  // 每头牛的环编号
set<int> pc[100005]; // 每个环的牛占据的位置
 
int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++)
        p[i] = i;
    for (int i = 0; i < k; i++) {
        scanf("%d %d", &ops[i].first, &ops[i].second);
        swap(p[ops[i].first], p[ops[i].second]);  // 求置换P
    }
    for (int i = 1; i <= n; i++) {                // 求环编号c[i]
        if (c[i]) continue;
        int x = p[i];
        c[i] = i;
        while (x != i) {
            c[x] = i;
            x = p[x];
        }
    }
    for (int i = 1; i <= n; i++)                  // 每个周期开始时的位置，加入环位置的集合中
        pc[c[i]].insert(i);
    for (int i = 0; i < k; i++) {                 // 模拟所有舞步，将牛会到达的位置加入环位置的集合
        int a = ops[i].first, b = ops[i].second;
        pc[c[a]].insert(b);
        pc[c[b]].insert(a);
        swap(c[a], c[b]);
    }
    for (int i = 1; i <= n; i++)
        printf("%d\n", pc[c[i]].size());
    return 0;
}