UPC 换位置游戏（BFS || 并查集判环）

换位置游戏

万物皆可图论

可以先跳过题面~

题目描述

N 个小朋友（编号为 1 到 N）正在玩一个换位置游戏。从左到右依次排列着 N 个凳子 （编号为 1 到 N，最左边的为 1 号凳子，最右边的为 N 号凳子），每个凳子上都有一个数字 （凳脚处红色数字），每个数字互不相同，且都是不超过 N 的正整数。

游戏开始前，1 号小朋友坐在 1 号凳子上，2 号小朋友坐在 2 号凳子上，然后依次下去， N 号小朋友坐在 N 号凳子上。比如当 N=4 时，游戏开始前小朋友们坐凳子的状态如下图 1 所示：

图 1 游戏开始前 4 位小朋友坐凳子的状态

坐定后，游戏开始。每位小朋友看一下自己坐的凳子凳脚处的数字，然后根据这个数字 找到相应号码的凳子。比如上面的例子，1 号小朋友凳脚处数字是 3，所以他到 3 号凳子上 坐下，2 号小朋友凳脚处数字是 1，所以他到 1 号凳子坐下，3 号小朋友凳脚处数字是 2，所 以他到 2 号凳子坐下，4 号小朋友凳脚处数字是 4，所以他到 4 号凳子坐下。经过一轮换位 置以后，4 个小朋友坐凳子的状态如下图 2 所示：

图 2 经过第 1 轮换位置后小朋友们坐凳子的状态

坐定后，每位小朋友再看一下自己凳脚的数字，按照凳脚的数字再继续换位置，第二轮 换位置的结果如下图 3 所示：

图 3 经过第 2 轮换位置后小朋友们坐凳子的状态

坐定后，每位小朋友再看一下自己凳脚的数字，按照凳脚的数字再继续换位置，第三轮 换位置的结果如下图 4 所示：

图 4 经过第 3 轮换位置后小朋友们坐凳子的状态

当第三轮换位置结束后，发现每位小朋友又各自坐到了游戏开始前的位置上，此时游戏结束。

从上面的过程我们可以发现，从游戏开始经过 3 轮换位置后又回到了游戏开始前坐凳子 的状态，但当 N 很大的时候，这个换位置过程非常复杂，请编程帮忙计算一下最少需要经 过多少轮换位置才能回到游戏开始前坐凳子的状态。

输入

输入共 2 行。

第 1 行是一个整数 N（1≤N≤1000），表示参加游戏的小朋友人数，当然也表示凳子的 数目。

第 2 行 N 个互不相同的正整数 Ki（1≤Ki≤N，且 1≤i≤N），Ki 表示第 i 把凳子凳脚处的数字。

输出

输出共 1 行。

表示小朋友们通过换位置后回到游戏开始前坐凳子的状态最少需要经过多少轮。测试数

据保证输出的结果不超出 20000000。

样例输入 Copy

3

1 2 3

样例输出 Copy

1

提示

输入有3把凳子。1号凳子凳脚处的数字为1，2号凳子凳脚处的数字为2，3号凳子凳脚处的数字为3。第1轮换位置后，1号小朋友仍然坐在1号凳子上，2号小朋友仍然坐在2号凳子上，3号小朋友仍然坐在3号凳子上。所以经过1轮就回到了游戏开始前状态。

对于60%的数据，1≤N≤500，且最少需要交换的轮数不超过10000。

对于100%的数据，1≤N≤1000，且最少需要交换的轮数不超过20000000。

题意： 给定n个小朋友和凳子，每次小朋友都去找凳子上的数字对应的凳子，问至少经过几轮可以恢复初始状态。

思路： （语言混乱ing）

抽象一下问题，按凳子建有向图，问所有点出去再回到该点的最短路。那么要想再次回到该点的话，经过的必定是一个环。所以我们可以从每个点出发bfs一下，求第二次经过该点的最短路。为什么是第二次捏？因为出去的时候是第一次~

再来考虑一个问题，我们如何处理求出来的每个点的最短路才可以达到最终答案。我一开始想的是最大值，但是他每个单位时间都是必须移动的，如果是最大值的话在形成回路后就应该静止不动了。要想构成一个周期的话，应该对所有的最短路径求一个最小公倍数。

现在的时间复杂度是O（n*n），那么我们可不可以优化一下呢~

好了现在想一下，根据题目描述，必定有几个环（或是两个点的线段），那么在环内，最短路是一样的，所以就不用重复求环内点的最短路，这时候可以用并查集求出每个环的点数，这时候的点数就是最短路啦。再对点数求一遍最小公倍数，就解决问题了~

这样看来，数据结构优化万岁hhh

代码：

BFS朴素版本

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
ll num[maxn],res[maxn];
ll dis[maxn],vis[maxn];
ll q[maxn],hh,tt=-1;
ll n;
ll gcd(int a,int b){
  return b==0?a:gcd(b,a%b);
}
ll lcm(int a,int b){
  return a/gcd(a,b)*b;
}
ll bfs(int u){
  for(int i=1;i<=n;i++){
    q[i]=0;vis[i]=0;dis[i]=0;
  }
  q[++tt]=u;
  vis[u]=1;
  while(hh<=tt){
    int x=q[hh++];
    if(vis[x]==2) return dis[x];
    if(vis[num[x]]&&num[x]!=u) continue;
    q[++tt]=num[x];
    vis[num[x]]++;
    dis[num[x]]=dis[x]+1;
  }
}
int main(){
  cin>>n;
  for(ll i=1;i<=n;i++) cin>>num[i];
  for(ll i=1;i<=n;i++)
    res[i]=bfs(i);
  //for(int i=1;i<=n;i++)
  //  cout<<"#"<<i<<" "<<res[i]<<endl;
  ll sum=1;
  for(ll i=1;i<=n;i++) 
    sum=lcm(sum,res[i]);
  cout<<sum<<endl;
  return 0;
}