fork download
copy 
  1. #include<bits/stdc++.h>
  2. const int MD=1e9+7;
  3. const int M=1e6;
  4. typedef long long ll;
  5. using namespace std;
  6. ll cnt;
  7. vector<int>v[M];
  8. int vis[M];
  9. void dfs(int u)
  10. {
  11. 	vis[u]=1;
  12. 	cnt++;
  13. 	for(auto &p:v[u])
  14. 	{
  15. 		if(!vis[p])
  16. 		dfs(p);
  17. 	}
  18. }
  19. int main(){
  20. 	int t;
  21. 	cin>>t;
  22. 	while(t--)
  23. 	{
  24. 		for(int i=0;i<=M;i++)
  25. 		{
  26. 			v[i].clear();
  27. 			vis[i]=0;
  28. 		}
  29.     ll ans=1;
  30.     int n;
  31.     cin>>n;
  32.     for(int i=1;i<=n;i++)
  33.     {
  34.     	int x;
  35.     	cin>>x;
  36.     	v[i].push_back(x);
  37.     }
  38.     for(int i=1;i<=n;i++)
  39.     {
  40.     	if(!vis[i])
  41.     	{
  42.     		cnt=0;
  43.     		dfs(i);
  44.     		ans=(ans*cnt/__gcd(ans,cnt))%MD;
  45.     	}
  46.     }
  47.     cout<<ans<<endl;
  48. 	}
  49. 	return 0;
  50. }
Success #stdin #stdout 0.01s 43408KB
comments (?)
stdin
copy 
3
5
3 4 5 2 1
3
2 3 1
14
2 1 5 4 3 9 8 7 6 14 13 12 11 10
stdout
copy 
6
3
2
https://ideone.com/jYANJW
language:
C++14 (gcc 8.3)
created:
6 years 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!