Help in PCYCLE

I am getting runtime error.
help?

link CodeChef: Practical coding for everyone

You are making it too complicated for yourself friend. There’s a very simple solution which I’m gonna explain below. If after reading following solution, you still wish to continue with your one, tell me. :slight_smile:

Solution:

Just see that we are given a permutation of number 1…N. Think about this as a directed graph, where, for every vertex i, there is a directed edge from i to p[i].

As you can see, each vertex is connected to exactly two vertices, (one incoming and one outgoing edge). So, conclusion of all this is, that each vertex is a part of exactly one cycle.

Now, just create an boolean[] visited array, and for every vertex for which visited[i] == false, run a dfs (or a simple loop, as told below). we know each vertex is a part of exactly one cycle, so all vetrex connected to current vertex is a part of same cycle as current vertex. Right?.. This will give us the required answer.

Trick => We know each and every vertex has out degree 1. why not simply use a variable x, initialise it to current vertex value, and run following loop.

while(!visited[x]){

cycle += a[x]+" ";

visited[x] = true;

x = a[x];

}

This part is not necessary, but reduces complexity of solution.

Feel free to ask anything. My solution here

1 Like

there are no multiple test cases, plz check u have input cin>>t also.
please read the question carefully my friend…:slight_smile:

there was one more mistake in your solution that you were also starting the cycle with a visited node i corrected it and your corrected solution is here

And @taran_1407 is saying correct, please also read his solution.
And again dont just implement your code, first think about what and how you are going to solve the question

1 Like

Thanks man for the insight…!!
Never thought that way…!!

thanks for the cin>>t …

Worked.!

No problem @strawhatdragon :slight_smile: