fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <numeric>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. // Function to compute the greatest common divisor (GCD)
  9. int gcd(int a, int b) {
  10.     while (b) {
  11.         a %= b;
  12.         swap(a, b);
  13.     }
  14.     return a;
  15. }
  16.  
  17. // Function to compute the least common multiple (LCM)
  18. int lcm(int a, int b) {
  19.     return a / gcd(a, b) * b;
  20. }
  21.  
  22. // Function to find the length of a cycle starting from a node
  23. int find_cycle_length(vector<int>& r, vector<bool>& visited, int start) {
  24.     int current = start;
  25.     int length = 0;
  26.  
  27.     while (!visited[current]) {
  28.         visited[current] = true;
  29.         current = r[current];
  30.         length++;
  31.     }
  32.  
  33.     return length;
  34. }
  35.  
  36. int main() {
  37.     int t;
  38.     cin >> t;
  39.  
  40.     while (t--) {
  41.         int n;
  42.         cin >> n;
  43.         vector<int> r(n + 1); // r[i] is 1-indexed
  44.         for (int i = 1; i <= n; i++) {
  45.             cin >> r[i];
  46.         }
  47.  
  48.         vector<bool> visited(n + 1, false);
  49.         int result = 1;
  50.  
  51.         // Traverse all nodes to find cycles
  52.         for (int i = 1; i <= n; i++) {
  53.             if (!visited[i]) {
  54.                 int cycle_length = find_cycle_length(r, visited, i);
  55.                 result = lcm(result, cycle_length);
  56.             }
  57.         }
  58.  
  59.         cout << result << endl;
  60.     }
  61.  
  62.     return 0;
  63. }
  64.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
5
2
2 1
5
2 3 4 5 1
5
2 1 4 2 3
5
4 1 1 5 4
10
4 3 9 1 6 7 9 10 10 3
stdout
copy 
2
5
2
3
12
https://ideone.com/D4hTbt
language:
C++ (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!