最小生成树 kruskal算法简介

 1 int cmp(const int i,const int j) {
 2     return w[i] < w[j];
 3 }
 4 int find(int x) {　　//并查集的查找函数 得到x的根节点
 5     return p[x] == x ? x : p[x] = find(p[x]);
 6 }
 7 int kruskal() {
 8     int ans = 0;
 9     for(int i = 0;i < n;i ++) p[i] = i;　　//初始化根节点
11     for(int i = 0;i < t;i ++) r[i] = i;　　//初始化r数组 代表边的编号
13     sort(r,r + t,cmp);　　//根据w数组排r的序　　一种间接排序思想　　得到按照边的大小排序之后原来边的”编号“
14     for(int i = 0;i < t;i ++) {
15         int e = r[i];　　//得到边的编号e
16         int x = find(u[e]);　　//得到起点的根节点
17         int y = find(v[e]);　　//得到终点的根节点
18         if(x != y) {　　//如果两个节点不在一个集合
19             ans = max(ans,w[e]);
20             p[x] = y;　　//合并两个集合
21         }
22     }
23     return ans;
24 }

p[x] = find(p[x])