思路
这道题很容易想到环。
判断每一个点,是否能不断地走,走到自己,如果不能输出$-1$。
否则答案就是每一个环的长度的最小公倍数(显而易见),这里如果直接这样是过不了的,只能过$9/15$。
我们到底没有考虑到什么呢?其实我们没考虑到这里的环长度如果是偶数的话,答案就会$\div 2$,因为这里的每一个点都走两个一半就到了原来的点。
代码
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 110;
int n;
int a[N];
bool vis[N];
LL gcd (LL x,LL y) {
if (x < y) return gcd (y,x);
if (!y) return x;
return gcd (y,x % y);
}
int main () {
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
LL ans = 1;
for (int i = 1;i <= n;i++) {
memset (vis,false,sizeof (vis));
int j = a[i];
LL res = 1;
vis[i] = true;
while (!vis[j]) {
vis[j] = true;
j = a[j];
res++;
}
if (j != i) {
ans = -1;
break;
}
if (res % 2 == 0) res /= 2;
ans = ans / gcd (ans,res) * res;
}
cout << ans << endl;
return 0;
}
大佬能解释一下为什么是所有环长度的最小公倍数吗?谢谢