 # Help in PCYCLE

I am getting runtime error.
help?

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. 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… 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

No problem @strawhatdragon 