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
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
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
Thanks man for the insight…!!
Never thought that way…!!
thanks for the cin>>t …
Worked.!