fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. ll gcd(ll a, ll b){
  6.     while(b){
  7.         ll t = a % b;
  8.         a = b;
  9.         b = t;
  10.     }
  11.     return a;
  12. }
  13.  
  14. ll lcm(ll a, ll b){
  15.     return (a / gcd(a, b)) * b;
  16. }
  17.  
  18. int main() {
  19.     ios::sync_with_stdio(false);
  20.     cin.tie(nullptr);
  21.  
  22.     int n;
  23.     cin >> n;
  24.  
  25.     vector<int> p(n + 1);
  26.     vector<vector<int>> graph(n + 1);
  27.  
  28.     for (int i = 1; i <= n; i++) {
  29.         cin >> p[i];
  30.  
  31.         // Make the graph undirected so BFS finds the whole component
  32.         graph[i].push_back(p[i]);
  33.         graph[p[i]].push_back(i);
  34.     }
  35.  
  36.     vector<int> vis(n + 1, 0);
  37.     ll ans = 1;
  38.  
  39.     for (int i = 1; i <= n; i++) {
  40.         if (vis[i]) continue;
  41.  
  42.         queue<int> q;
  43.         q.push(i);
  44.         vis[i] = 1;
  45.  
  46.         int sz = 0;
  47.  
  48.         while (!q.empty()) {
  49.             int u = q.front();
  50.             q.pop();
  51.             sz++;
  52.  
  53.             for (int v : graph[u]) {
  54.                 if (!vis[v]) {
  55.                     vis[v] = 1;
  56.                     q.push(v);
  57.                 }
  58.             }
  59.         }
  60.  
  61.         ans = lcm(ans, (ll)sz);
  62.     }
  63.  
  64.     cout << ans << "\n";
  65. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
4
3 4 2 1
stdout
copy 
4
https://ideone.com/YSnLI5
language:
C++ (gcc 8.3)
created:
9 hours 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!