hdu1856 选出更多的孩子

时间:2022-06-09 16:45:23

题目大意:

老师选取2个学生对应的号码,这两人视作朋友,同时朋友的朋友也可以看成自己的朋友。

最后老师选出一个人数最多的朋友圈。

这里学生的人数不大于10^7,所以操作时需要极为注意,操作步数能省则省。

我也在超时了两次之后,不断进行代码优化才做出。

超时的部分函数代码:

 int getHead(int x)
{
while(x!=fa[x]) x=fa[x];
return x;
}

后来在这个代码基础上加了int a=x;return前加一个fa[a]=x;这样在查找顶点时,同时将路径进行压缩,下次再去查找时就不会有重复的操作。

之前的联合函数
void Union(int x,int y)
{

    int
fa_x=getHead(x);
    int
fa_y=getHead(y);
    if
(fa_x!=fa_y) {fa[fa_x]=fa_y;K[fa_y]+=K[fa_x];}
}

这是将每个作为顶点位置上对应的小组人数保存在K数组中,但是这样在main函数中要对K数组进行一次遍历(10^7次的操作,又浪费时间了)
所以后来引进了Max的全局变量,每次结合时就更新Max,那么main函数中直接输出Max即可.

改过之后函数变为:

void Union(int x,int y)
{

    int
fa_x=getHead(x);
    int
fa_y=getHead(y);
    if
(fa_x!=fa_y) {fa[fa_x]=fa_y,fa[x]=fa_y;K[fa_y]+=K[fa_x];}
    Max=max(Max,K[fa_y]);
}

总体代码如下:

 #include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 10000100
int Max;
int fa[MAXN],K[MAXN]; int max(int x,int y)
{
return x>y?x:y;
}
int getHead(int x)
{
int a=x;
while(x!=fa[x]) x=fa[x];
fa[a]=x;
return x;
}
void Union(int x,int y)
{
int fa_x=getHead(x);
int fa_y=getHead(y);
if(fa_x!=fa_y) {fa[fa_x]=fa_y,fa[x]=fa_y;K[fa_y]+=K[fa_x];}
Max=max(Max,K[fa_y]);
}
int main()
{
int n,t;
while(scanf("%d",&n)!=EOF){
t=;
int *a=new int[n];
int *b=new int[n];
for(int i=;i<=MAXN;i++){
K[i]=;
fa[i]=i;
}
Max=;
for(int i=;i<n;i++){
scanf("%d%d",&a[i],&b[i]);
Union(a[i],b[i]);
} printf("%d\n",Max);
}
return ;
}