题目大意:
老师选取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 ;
}