转自hwzzyr的博客 kruskal重构树 由于重构树中把原树的点权转换成为了新建节点的边权，这一过程是这样实现的。 首先对边排序 然后使用并查集辅助加边，每新建一条边时： 新建节点indexindex（编号从n+1n+1开始） 将原有两节点所在集合改为indexindex 将原有节点与indexindex连边 新建节点的权值为当前边的边权 给一下简单的代码
void Ex_Kruskal() { int ind=n,lim=n<<1; sort(e+1,e+1+m); for(int i=1;i<=lim;++i) f[i]=i; for(int i=1;i<=m;++i) { int fx=getfa(e[i].a),fy=getfa(e[i].b); if(fx!=fy) { f[fx]=f[fy]=++ind; val[ind]=e[i].w; add(ind,fx); add(ind,fy); if(ind==lim-1) break; } } return ; }代码复杂度很低，时间复杂度是优秀的O(nlog2n)
例题bzoj3732
#include<cstdio> #include<algorithm> using namespace std; const int N=3e4+2; int n,m,q,cnt; int fa[N<<1],f[N<<1][20],dep[N<<1],val[N<<1],g[N<<1][2]; int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);} struct data{ int u,v,w; bool operator<(const data &a)const{return w<a.w;} }e[N<<1]; inline int ask(int u,int v){ if(dep[u]<dep[v])swap(u,v); int t=dep[u]-dep[v]; for(int i=0;i<20;i++)if(t&(1<<i))u=f[u][i]; for(int i=19;~i;i--)if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i]; if(u!=v)u=f[u][0]; return u; } inline void dfs(int u){ if(!g[u][0])return; dep[g[u][0]]=dep[g[u][1]]=dep[u]+1; dfs(g[u][0]),dfs(g[u][1]); } int main(){ scanf("%d%d%d",&n,&m,&q),cnt=n; for(int i=0;i<m;i++)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); sort(e,e+m); for(int i=1;i<=n;i++)fa[i]=i,fa[i+n]=i+n; for(int i=0;i<m;i++){ int u=e[i].u,v=e[i].v; if(getfa(u)==getfa(v))continue; g[++cnt][0]=fa[u],g[cnt][1]=fa[v]; fa[fa[u]]=fa[fa[v]]=f[fa[u]][0]=f[fa[v]][0]=cnt; val[cnt]=e[i].w; } dfs(cnt); for(int j=1;j<20;j++) for(int i=1;i<=cnt;i++)f[i][j]=f[f[i][j-1]][j-1]; for(int x,y,i=0;i<q;i++){ scanf("%d%d",&x,&y); printf("%d\n",val[ask(x,y)]); } return 0; }转载于:https://www.cnblogs.com/MikuKnight/p/9865550.html
相关资源：JAVA上百实例源码以及开源项目