(l2-026) small generation (with weight and search set)

Topic link ：PTA | Program design experiment auxiliary teaching platform

The title requires the number of the member with the lowest seniority , Obviously, the maintenance between generations can be realized by weighted and search set , Distance indicates seniority ,  Then the rest is a basic weighted and search set template , It should be noted that after we have processed all the merging operations, we need to perform another merging on all points find operation , Ensure that each point is d The arrays are completely updated , Because of our find Operation with update distance in operation , Every time find(x) The operation will only update x And all of its ancestors d Array , Arrays outside this range will not be updated , Because of our merge The operation does not find the real d value , Just put his d The array is set to its parent node +1, But his father's node d Array values are not necessarily correct , Maybe it's just a parent node that depends on his father node , So after we deal with all the relationships, we need to deal with 1~n The number in find operation , Only in this way can we ensure the final d The array value is correct , Here is the code ：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<set>
#include<vector>
#include<map>
#include<queue>
#include<cmath>
using namespace std;
const int N=100003;
int fu[N],d[N],ans[N],tt;
int find(int x)
{
	int t=fu[x];
	if(x==fu[x]) return x;
	fu[x]=find(fu[x]);
	d[x]+=d[t];
	return fu[x];
}
void merge(int x,int y)
{
	int fx=find(x),fy=find(y);
	if(fx==fy) return ;
	fu[fx]=fy;
	d[x]=1+d[y];
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		fu[i]=i;
	int t;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&t);
		if(t==-1) continue;
		merge(i,t);
	}
	for(int i=1;i<=n;i++) find(i);// Update  
	int mx=0;
	for(int i=1;i<=n;i++)
		mx=max(mx,d[i]);
	printf("%d\n",mx+1);
	for(int i=1;i<=n;i++)
		if(d[i]==mx) ans[++tt]=i;
	for(int i=1;i<=tt;i++)
	{
		printf("%d",ans[i]);
		if(i!=tt) printf(" ");
	}
	return 0;
}