получить ошибку при возвращении значения, но исправить при передаче по ссылке

Question

n детей, каждый из которых читает уникальную книгу. В конце любого дня i-тый ребенок отдаст свою книгу пи-тому ребенку (в случае i = pi ребенок отдаст свою книгу самому себе). Гарантируется, что все значения числа pi являются различными целыми числами от 1 до n (т.е. p является перестановкой). Последовательность p не меняется изо дня в день, она фиксирована.

Например, если n = 6 и p = [4,6,1,3,5,2], то в конце в первый день книга 1-го ребенка будет принадлежать 4-му ребенку, 2-й ребенок будет принадлежать 6-му ребенку и так далее. В конце второго дня книга 1-го ребенка будет принадлежать 3-му ребенку, 2-й ребенок будет принадлежать 2-му ребенку и т. Д.

Ваша задача чтобы определить номер дня, когда книга i-го ребенка возвращается ему впервые для каждого i от 1 до n.

Рассмотрим следующий пример: p = [5,1, 2,4,3]. Книга 1-го ребенка будет передана следующим детям:

после 1-го дня она будет принадлежать 5-му ребенку, после 2-го дня она будет принадлежать 3 3-й ребенок, после 3-го дня он будет принадлежать 2-му ребенку, после 4-го дня он будет принадлежать 1-му ребенку. Так что после четвертого дня книга первого малыша вернется к своему владельцу. Книга четвертого ребенка вернется к нему впервые через ровно один день.

Вы должны ответить на q независимых запросов

Использованный подход
DISJOINT SETS
если 1 дает 4, а затем находит родителя 1 и 4. Если разные родители затем выполняют объединение 1 и 4, еще переходят к следующей паре
Наконец, и по размеру набора он принадлежит

eg-
1
6
4 6 2 1 5 3

// код, дающий правильный ответ при передаче p по ссылке в 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;
}

// код, дающий неправильный ответ, когда значение возвращается функцией 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;
}

Answer 1

Вторая версия демонстрирует неопределенное поведение. Если вы посмотрите поближе, вы увидите, что вы не всегда возвращаете значение.

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
    }
}

Правильно будет

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
    }
}

---

Ваш компилятор также должен предупредить вас об этом, поэтому включите все предупреждения и прослушайте их.