codefores741A Arpa's loud Owf and Mehrdad's evil plan(图找环)-白红宇

codefores741A Arpa's loud Owf and Mehrdad's evil plan(图找环)

阅读量：6988 次

发布时间：2019-06-27

本文共 1292 字，大约阅读时间需要 4 分钟。

题意：

对于给定的一个数列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
    
     #include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #include
           
            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); else return 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

你可能感兴趣的文章