C. Arpa's loud Owf and Mehrdad's evil plan
time limit per test
memory limit per test
input
output
As you have noticed, there are lovely girls in Arpa’s land.
1 to n. Everyone has exactly one crush, i-th person's crush is person with the number crushi.
Owf
x wants to start a round, he calls crushx and says: "Oww...wwf" (the letter w is repeated t times) and cuts off the phone immediately. If t > 1 then crushx calls crushcrushx and says: "Oww...wwf" (the letter w is repeated t - 1times) and cuts off the phone immediately. The round continues until some person receives an "Owf" (t = 1). This person is called the Joon-Joon
t (t ≥ 1) such that for each person x, if x starts some round and y becomes the Joon-Joon of the round, then by starting from y, x would become the Joon-Joon of the round. Find such t
crushi = i).
Input
n (1 ≤ n ≤ 100) — the number of people in Arpa's land.
n integers, i-th of them is crushi (1 ≤ crushi ≤ n) — the number of i-th person's crush.
Output
t satisfying the condition, print -1. Otherwise print such smallest t.
Examples
input
4 2 3 1 4
output
3
input
4 4 4 4 4
output
-1
input
4 2 1 4 3
output
1
遍历每个人i, 用深搜找到是否存在从第i个人出发，经过次数t回到第i个人的情况，若不存在无解，若存在判断t是否为偶数，若为偶数则除以2，求出所有t的最小公倍数就是答案
#include <bits/stdc++.h>
#define MOD 1000000007
#define maxn 100005
using namespace std;
typedef long long ll;
int num[105];
int vis[105], t[105], cnt, k;
bool dfs(int j){
if(num[j] == k){
return true;
}
int h = num[j];
if(vis[h])
return false;
vis[h] = 1;
cnt++;
if(dfs(h))
return true;
return false;
}
ll gcd(ll a, ll b){
return b ? gcd(b, a % b) : a;
}
int main(){
// freopen("in.txt", "r", stdin);
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", num+i);
for(int i = 1; i <= n; i++){
memset(vis, 0, sizeof(vis));
cnt = 1;
vis[i] = 1;
k = i;
if(dfs(i) == false){
puts("-1");
return 0;
}
if(cnt&1)
t[i] = cnt;
else
t[i] = cnt / 2;
}
ll ans = t[1];
for(int i = 2; i <= n; i++){
ans = ans * t[i] / gcd((ll)ans, (ll)t[i]);
}
printf("%I64d\n", ans);
return 0;
}