[URI ONLINE JUDGE] – 2063 – Hunting Digletts

Diglett is a Pokémon type of land that is digging underground tunnels and is almost never seen. It appears on the surface through a hole in the ground time to time, where you can view only his head.

Digglets

The tunnels built by them are unidirectional and always connect an origin hole to a destination hole, for example: if there is a tunnel connecting the hole A to the hole B, then it is possible to go from A to B and not the opposite. Each Diglett has its own hole, which indicates that there N holes will be N Digletts. Each hole has exactly two tunnels: the first tunnel, which runs from it to another hole and the second tunnel, which comes to him from another hole.

The Digletts are walking from hole to hole every moment of time, for example: consider a hole A that has a tunnel that connects to a hole B, if one Diglett in the hole A at time T, then the next moment of time T+1 it will be in the hole B. When a Diglett arrives at his hole, it appears immediately on the surface. When not in his hole, it just remains underground and waiting for the next moment of time to walk the tunnel and go to another hole. It is guaranteed that each Diglett always returns to its hole in a moment of time.

Xisto is a Pokémom Master and is looking to capture the greatest amount of Digletts with only a pokeball, this in turn is able to capture all visible Digletts in a given area. He needs your help to know what is the shortest time in which all Digletts will appear on the surface at the same time, so he could throw the pokeball and catch them all.

Note: At time zero Digletts are all in their respective hole and does not appear on the surface.

Input

The first row contains an integer N (2 ≤ N ≤ 100) representing the amount of holes. The next line contains N integers Bi (1 ≤ Bi ≤ N), where the i-th integer representing the i-th hole, and indicates a unidirectional tunnel i-th hole to Bi hole.

Output

Print the shortest time in which all Digletts will appear together on the surface.

Input Samples Output Samples
2

2 1

2
4

4 3 2 1

2
6

2 1 5 3 6 4

4

 

solution:

 

<br /> 

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
int n;
int G[105];

int res = 1;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> G[i];
}

for(int i = 1; i <= n; i++) {
int p = G[i];
int t = 1;
while(p != i) {
t++;
p = G[p];
}
res = (res/__gcd(res, t)) * t;
}
cout << res << endl;

return 0;
}

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s