SHARE
TWEET

Pow

warriorscats Jun 6th, 2020 (edited) 904 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <fstream>
  2. #include <vector>
  3. #include <set>
  4. #include <cstdio>
  5. #include <cctype>
  6.  
  7.  
  8. #define BUFFER_SIZE 1000001
  9.  
  10. ///std::ifstream fin ("permutarepow.in");
  11. std::FILE *fin = std::fopen ("permutarepow.in", "r");
  12. std::ofstream fout ("permutarepow.out");
  13.  
  14. char buffer[BUFFER_SIZE];
  15. int pos = -1;
  16.  
  17. inline void read_buffer ()
  18. {
  19.     std::fread (buffer, sizeof (char), BUFFER_SIZE, fin);
  20. }
  21.  
  22. inline char read_utility ()
  23. {
  24.     ++ pos;
  25.     if (pos == BUFFER_SIZE)
  26.     {
  27.         read_buffer ();
  28.         pos = 0;
  29.     }
  30.  
  31.     return buffer[pos];
  32. }
  33.  
  34. inline char read_char ()
  35. {
  36.     char ans;
  37.     while (std::iswspace (ans = read_utility ()));
  38.  
  39.     return ans;
  40. }
  41.  
  42. inline long long read_int ()
  43. {
  44.     char c;
  45.     while (!std::isdigit (c = read_utility ()));
  46.  
  47.     int ans = 0;
  48.     while (std::isdigit (c))
  49.     {
  50.         ans = ans * 10 + (c - '0');
  51.         c = read_utility ();
  52.     }
  53.  
  54.     return ans;
  55. }
  56.  
  57. long long n, period = 1;
  58. std::vector <std::vector <long long>> Graph;
  59. std::set <long long> Store;
  60. std::vector <bool> Seen;
  61.  
  62. inline long long cmmdc (long long n, long long m)
  63. {
  64.     if (!m)
  65.         return n;
  66.     else
  67.         return cmmdc (m, n % m);
  68. }
  69.  
  70. inline long long cmmmc (long long n, long long m)
  71. {
  72.     return ((n * m) / cmmdc (n, m));
  73. }
  74.  
  75. inline void DFS_Traversal (long long src, long long &conex)
  76. {
  77.     ++ conex; Seen[src] = true;
  78.  
  79.     for (auto u : Graph[src])
  80.         if (!Seen[u])
  81.             DFS_Traversal (u, conex);
  82. }
  83.  
  84. int main ()
  85. {
  86.     n = read_int ();
  87.  
  88.     Graph = std::vector <std::vector <long long>> (n + 1);
  89.     Seen = std::vector <bool> (n + 1, false);
  90.  
  91.     for (long long i = 1; i <= n; ++ i)
  92.         Graph[i].push_back (read_int ());
  93.     ///fin.close ();
  94.  
  95.     for (long long i = 1; i <= n; ++ i)
  96.     {
  97.         if (!Seen[i])
  98.         {
  99.             long long conex = 0;
  100.             DFS_Traversal (i, conex);
  101.             Store.insert (conex);
  102.             ///fout << conex << "\n";
  103.         }
  104.     }
  105.  
  106.     for (auto it : Store)
  107.         period = cmmmc (it, period);
  108.  
  109.     fout << period; fout.close ();
  110.  
  111.     return 0;
  112. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top