There are n kids, each of them is reading a unique book. At the end of any day, the i-th kid will give his book to the pi-th kid (in case of i=pi the kid will give his book to himself). It is guaranteed that all values of pi are distinct integers from 1 to n (i.e. p is a permutation). The sequence p doesn't change from day to day, it is fixed.
For example, if n=6 and p=[4,6,1,3,5,2] then at the end of the first day the book of the 1-st kid will belong to the 4-th kid, the 2-nd kid will belong to the 6-th kid and so on. At the end of the second day the book of the 1-st kid will belong to the 3-th kid, the 2-nd kid will belong to the 2-th kid and so on.
Your task is to determine the number of the day the book of the i-th child is returned back to him for the first time for every i from 1 to n.
Consider the following example: p=[5,1,2,4,3]. The book of the 1-st kid will be passed to the following kids:
after the 1-st day it will belong to the 5-th kid, after the 2-nd day it will belong to the 3-rd kid, after the 3-rd day it will belong to the 2-nd kid, after the 4-th day it will belong to the 1-st kid. So after the fourth day, the book of the first kid will return to its owner. The book of the fourth kid will return to him for the first time after exactly one day.
You have to answer q independent queries
Approach used
DISJOINT SETS
if 1 gives to 4 then find parent of 1 and 4.If differnt parents then perform union of 1 and 4 else move to next pair
At last ans is size of set it belongs to
eg-
1
6
4 6 2 1 5 3
//code giving correct answer when passed p by reference in findparent
#include<bits/stdc++.h>
using namespace std;
void findparent(int num,vector<int> s,int &p)
{
if(s[num]<0)
{
p=num;
return;
}
else
{
findparent(s[num],s,p);
}
}
int main()
{
int q;
cin>>q;
while(q)
{
int n;
cin>>n;
vector<int> v(n+1,0);
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
v[i]=x;
}
vector<int> s(n+1,-1);
for(int i=1;i<=n;i++)
{
int a=i;
int b=v[i];
int pa;
findparent(a,s,pa);
int pb;
findparent(b,s,pb);
if(pa!=pb)
{
//union(a,b);
if(s[pa]<=s[pb])//negative values being considered
{
s[pa]=s[pa]+s[pb];
s[pb]=pa;
}
else
{
s[pb]=s[pa]+s[pb];
s[pa]=pb;
}
}
}
vector<int> ans(n+1);
for(int i=1;i<=n;i++)
{
int p;
findparent(i,s,p);
ans[i]=-s[p];
cout<<ans[i]<<" ";
}
cout<<endl;
q--;
}
return 0;
}
//code giving wrong answer when value is returned by the function findparent
#include<bits/stdc++.h>
using namespace std;
int findparent(int num,vector<int> s)
{
if(s[num]<0)
{
return num;
}
else
{
findparent(s[num],s);
}
}
int main()
{
int q;
cin>>q;
while(q)
{
int n;
cin>>n;
vector<int> v(n+1,0);
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
v[i]=x;
}
vector<int> s(n+1,-1);
for(int i=1;i<=n;i++)
{
int a=i;
int b=v[i];
int pa=findparent(a,s);
int pb=findparent(b,s);
if(pa!=pb)
{
//union(a,b);
if(s[pa]<=s[pb])//negative values being considered
{
s[pa]=s[pa]+s[pb];
s[pb]=pa;
}
else
{
s[pb]=s[pa]+s[pb];
s[pa]=pb;
}
}
}
vector<int> ans(n+1);
for(int i=1;i<=n;i++)
{
int p=findparent(i,s);
ans[i]=-s[p];
cout<<ans[i]<<" ";
}
cout<<endl;
q--;
}
return 0;
}
The second version exhibits undefined behaviour. If you take a closer look, you see, that you don't always return a value.
int findparent(int num,vector<int> s)
{
if(s[num]<0)
{
return num; // Here you return something
}
else
{
findparent(s[num],s); // Here you return nothing
}
}
Correct would be
int findparent(int num, vector<int> s)
{
if(s[num]<0)
{
return num; // Here you return something
}
else
{
return findparent(s[num],s); // return the result of the recursive call
}
}
Your compiler should also warn you about this, so turn on all the warnings and listen to them.