題意：

對于給定的一個數列a[n],如果現在點i，那么下一個點就在a[i]，現在問給定n個點，找到一個最小的t,使得對于從任意一個點x出發，經過t次之后，到達的點y, 使得點y經過t次之后會回到點x。

要點：

一看就是圖找環，找到所有獨立的環對應的節點數，對所有節點數求最小公倍數就是結果。有個地方要注意就是，當節點數是偶數時，比如1->2->3->4->1，這種情況要將節點數/2計算，因為比如1到達3要2次，3到達1也是兩次，肯定比從1繞一圈再到1要小，奇數沒有辦法。

#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<map> #include<queue> #include<vector> #include<algorithm> using namespace std; typedef long long ll; const int N = 105; int a[N], vis[N]; ll b[N];int dfs(int u, int s, int l)//有向圖找環 {if (u == s) {l = l + 1;return l;}if (vis[u] && u != s) {return -1;}vis[u] = 1;if (a[u] == s)return dfs(a[u], s, l);elsereturn dfs(a[u], s, l + 1); } ll gcd(ll a, ll b) {if (b == 0) return a;return gcd(b, a%b); }int main() {int n;scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);memset(vis, 0, sizeof(vis));int cnt = 0;bool flag = true;for (int i = 1; i <= n; i++){if (vis[i])continue;int temp = dfs(a[i], i, 1);if (temp != -1){if (temp % 2 == 0)temp /= 2;b[cnt++] = temp;}else{flag = false;break;}}if (!flag)printf("-1\n");else{ll lcm, c = b[0], e;for (int i = 0; i < cnt; i++)//計算lcm{e = gcd(c, b[i]);lcm = c*b[i] / e;c = lcm;}printf("%I64d\n", lcm);}return 0; }

轉載于:https://www.cnblogs.com/seasonal/p/10343651.html

總結

以上是生活随笔為你收集整理的codefores741A Arpa's loud Owf and Mehrdad's evil plan(图找环)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。