return 值时出错，但按引用传递时答案正确

Question

有n个孩子，他们每个人都在读一本不同的书。在任何一天结束时，i-th 孩子都会把他的书给 pi-th 孩子（如果 i=pi，孩子会把他的书给自己）。保证 pi 的所有值都是从 1 到 n 的不同整数（即 p 是一个排列）。序列p每天都没有变化，它是固定的。

例如，如果 n=6 且 p=[4,6,1,3,5,2] 那么在第一天结束时，第 1 个孩子的书将属于第 4-第 th 个孩子，第 2 个孩子将属于第 6 个孩子，依此类推。第二天结束时，第一个孩子的书归第三个孩子，第二个孩子的书归第二个孩子，依此类推

你的任务是确定 i-th child 的书第一次 return 返回给他的天数，每个 i 从 1 到 n .

考虑以下示例：p=[5,1,2,4,3]。第一个孩子的书将传给以下孩子：

第 1 天后，它将属于第 5 个孩子，第二天之后，它将属于第三个孩子，第三天之后，它将属于第二个孩子，第 4 天后，它将属于第一个孩子。所以在第四天之后，第一个孩子的书将 return 交给它的主人。正好一天后老四的书会return第一次给他

您必须回答 q 个独立的问题

使用的方法
不相交集
如果 1 给 4 然后找到 parent of 1 和 4.If differnt parent 然后执行 1 和 4 的并集否则移动到下一对
最后 ans 是它所属的集合的大小

如-
1
6
4 6 2 1 5 3

//在 findparent

中通过引用传递 p 时给出正确答案的代码

#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

第二个版本表现出未定义的行为。如果仔细观察，您会发现您并不总是 return 一个值。

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

您的编译器也应该对此发出警告，因此请打开所有警告并听取它们。

return 值时出错，但按引用传递时答案正确

getting error when return value but correct ans when pass by reference

c++

disjoint-sets