假设第i条边的两个端点序号和权值分别保存在u[i],v[i],w[i]中，排序后第i小的边的序号保存在r[i]中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int cmp(const int i, const int j) {return w[i]<w[j];}
int find(int x) { return p[x]==x ? x:p[x]=find(p[x]);}
int Kruskal()
{
	int ans=0;
	for(int i=0;i<n;i++) p[i]=i;
	for(int i=0;i<m;i++) r[i]=i;
	sorted(r,r+m,cmp);
	
	for(int i=0;i<m;i++)
	{
		int e=r[i]; int x=find(u[e]); int y=find(v[e]);
		
		if(x!=y) {ans+=w[e];p[x]=y;}
	}
	return ans;
}

摘自白书