并查集有两种优化。第一种是直接连根——虽然是O(n)但是会破坏树形结构。
按秩合并
大意：求最小生成树的两个点间的最大路径。
带边权的并查集？多组数据？
我们按秩合并。
基本思想是使包含较少结点的树的根指向包含较多结点的树的根。
我们存边时，用结构体存边。但不用前向星。因为如果要kruskal的话需要改动一下。本来我们连接最短的边时，如果两端的端点的父亲不一样的话直接连上就可以了。但是按秩排序不一样。他既要优化又要不破坏树形结构，我们就造一个秩rank，rank[i]表示的相当于子树大小或者深度的东西，每次查询就把小的连到大的上并直接把边权直接连到父亲结点上，那么就能保留原来的树形结构并做到优化。
#include<iostream> #include<cstdio> #include<algorithm> #include<ctype.h> #include<cstring> using namespace std; const int maxn=50010; inline int read() { int x=0,w=1;char c=getchar(); while(!isdigit(c)){ if(c=='-')w=-1; c=getchar(); } while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x*w; } int n,m,t; int fa[maxn],e[maxn],rank[maxn]; struct data{ //这是边 int x,y,z; }a[maxn]; inline bool cmp(data a,data b){return a.z<b.z;} inline int find(int x){return fa[x]==x?x:find(fa[x]);} inline void kruskal() { int s=0,f1,f2; for(int i=1;i<=n;i++)fa[i]=i,rank[i]=1; for(int i=1;i<=m;i++) { f1=find(a[i].x); f2=find(a[i].y); if(f1!=f2) { if(rank[f1]<rank[f2]) { fa[f1]=f2; e[f1]=a[i].z; rank[f2]=max(rank[f2],rank[f1]+1); }//高度大的做小的的根 else{ fa[f2]=f1; e[f2]=a[i].z; rank[f1]=max(rank[f1],rank[f2]+1); }//相等或者相反就相反来 s++; } if(s==n-1)break; } } int c[maxn]; int query(int x,int y) { for(int i=1;i<=n;i++)c[i]=-1; int tmp=0,ans=0; while(1) { c[x]=tmp;//c是从x开始向上边的最大值。 if(fa[x]==x)break; tmp=max(tmp,e[x]);//e代表向上连接的边权 x=fa[x];//向上爬 } while(1) { if(c[y]>=0){ans=max(ans,c[y]);break;}//找到LCA就break if(fa[y]==y)break;//或者找到根 ans=max(ans,e[y]); y=fa[y]; }//因为一定会集中到LCA就直接用ans return ans; } int main() { while(~scanf("%d%d",&n,&m)) { for(int i=1;i<=m;i++) { a[i]=(data){read(),read(),read()}; } sort(a+1,a+1+m,cmp); kruskal(); t=read(); for(int x,y,i=1;i<=t;i++){ x=read(),y=read(); printf("%d\n",query(x,y)); } } return 0; }
但是按秩合并并不仅仅能够处理最小生成树问题，也可以处理一些大规模数据的动态加边和查询问题，每次连边后可以记录两个秩的大小，非常的方便。