fork download
copy 
  1. /***>              @author : a_e_kasem              <***/
  2. //                        ﷽
  3. //                  { وَأَنْ لَيْسَ لِلْإِنْسَانِ إِلَّا مَا سَعَى }
  4. //
  5. //         فَالجُهدُ يُثمِرُ إنْ تَضافَرَ صَفوُهُ، والعَزمُ يَرفعُ صَرحَ كُلِّ بُنيانِ
  6. //
  7. //                    وَما نَيلُ المَطالِبِ بِالتَمَنّي
  8. //                     وَلَكِن تُؤخَذُ الدُنيا غِلابا
  9. //                           ***
  10. //                   وَما اِستَعصى عَلى قَومٍ مَنالٌ
  11. //                   إِذا الإِقدامُ كانَ لَهُم رِكابا
  12. //
  13. #include <bits/stdc++.h>
  14. using namespace std;
  15.  
  16. #define int long long
  17. #define cinAll(a) for (auto &it : a) cin >> it
  18. #define all(x) (x).begin(), (x).end()
  19. #define NO  void(cout << "NO\n")
  20. #define YES void(cout << "YES\n")
  21.  
  22. const int N = 2e5 + 5;
  23. vector<int> G[N];
  24. vector<vector<int>> All_path;
  25. vector<int> path;
  26. vector<int> vst;
  27.  
  28.  
  29.  
  30. void solve() {
  31.     int n; cin >> n;
  32.     vector<int> p(n+1);
  33.     for (int i = 1; i <= n; i++) cin >> p[i];
  34.  
  35.     for (int i = 1; i <= n; i++) {
  36.         G[i].clear();
  37.     }
  38.     path.clear();
  39.     All_path.clear();
  40.     vst.assign(n+1, 0);
  41.  
  42.  
  43.     int root = 0;
  44.     for (int i = 1; i <= n; i++) {
  45.         if (i == p[i]) {
  46.             root = i;
  47.             continue;
  48.         }
  49.         G[p[i]].push_back(i);
  50.     }
  51.  
  52.     for (int i = 1; i <= n; i++)
  53.     {
  54.         if (G[i].size() > 0)
  55.         {
  56.             continue;
  57.         }
  58.  
  59.         vector<int >path;
  60.         int nd = i;
  61.         while (!vst[nd])
  62.         {
  63.             path.push_back(nd);
  64.             vst[nd] = 1;
  65.             nd = p[nd];
  66.         }
  67.  
  68.         reverse(all(path));
  69.         All_path.push_back(path);
  70.     }
  71.  
  72.  
  73.     cout << All_path.size() << "\n";
  74.     for (auto &vec : All_path) {
  75.         cout << vec.size() << "\n";
  76.         for (auto x : vec) cout << x << " ";
  77.         cout << "\n";
  78.     }
  79.     cout << "\n";
  80. }
  81.  
  82.  
  83.  
  84.  
  85. void FastIO();
  86. int32_t main() {
  87.     FastIO();
  88.  
  89.     int t = 1;
  90.     cin >> t;
  91.     while(t--)
  92.     {
  93.         solve();
  94.     }
  95.  
  96.     return 0;
  97. }
  98.  
  99. void FastIO()
  100. {
  101.     // freopen("input.txt", "r", stdin);
  102.     // freopen("output.txt", "w", stdout);
  103.     ios::sync_with_stdio(false);
  104.     cin.tie(nullptr);
  105.     cout.tie(nullptr);
  106. }
Success #stdin #stdout 0.01s 8348KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/r7Tob9
language:
C++14 (gcc 8.3)
created:
3 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!