codeforces 742c Arpa's loud Owf and Mehrdad's evil plan

codeforces 742c Arpa's loud Owf and Mehrdad's evil plan

题意

给定一个有向图，每个点出度为1，各个边长度为1。
求一个最小的k，使得对于每个点，经过k长度到达y，从y出发经过k到达原点。

思路

如果存在k，那么有向图一定由多个环组成。
k即为每个奇数环长度和每个偶数环1/2长度的最小公倍数。

代码

#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
vector <int>ans;
int n,c[110],visit[110];
long long gcd(long long a,long long b){return a == 0?b:gcd(b%a,a);
}
int dfs(int u,int st,int d){visit[u] = 1;if(c[u] == st) return d+1;else if(visit[c[u]]) return -1;return dfs(c[u],st,d+1);
}
int main(){scanf("%d",&n);for(int i = 1;i <= n;i ++) scanf("%d",&c[i]);int flag = 1;for(int i = 1;i <= n;i ++){if(!visit[i]) {int tmp = dfs(i,i,0);if(tmp == -1) {flag = -1;break;}else ans.push_back(tmp);}}if(flag == -1) printf("-1n");else{long long numans = 1;flag = 1;for(int i = 0;i < ans.size();i ++){long long tmp = ans[i]%2?ans[i]:ans[i]/2;numans = numans * tmp / gcd(numans,tmp); if(i != 0 && flag && ans[i] != ans[i - 1]) flag = 0;}printf("%I64dn",numans);}return 0;
}