题目传送门

这道题的正解是逆向思路，从N枚举到K，并逐渐往并查集里添加

我有一个想法，就是说能不能在读入的时候就全部加入集合里，并将大的的父亲都设置成小的，然后正序枚举，观察等于k的数量是否大于n/2

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
int num,ans;
int n,a,h;
int fa[MAXN];
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-'){w=-1;}ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
void write(int x) 
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int find(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void join(int x,int y)
{
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy)
	{
		fa[fx]=fy;
	}
}

int main()
{
	n=read();
	for (int i=1;i<=n;i++)
	{
		fa[i]=i;
	}
	for (int i=1;i<=n;i++)
	{
		a=read();
		for (int j=1;j<=a;j++)
		{
			h=read();
			int x=i,y=h;
			if(y>x) swap(x,y);
			join(x,y);
		}
	}
	/*for (int i=1;i<=n;i++)
	{
		cout<<fa[i]<<" ";
	}*/
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
		{
			//cout<<find(j)<<" "<<i<<endl;
			if(fa[j]==i)
			{
				//fa[j]=0;
				num++;
				if(num>n/2)
				{
					write(i);
					return 0;
				}
			}
		}
	}
	return 0;
}