空间压缩前算法版本
/*
第一次接触并查集是在紫书上的kruskal上学的。当时作者对边排序的时候用的是,间接排序,很懵,看不懂啊。于是根据自己以往的学习,此处只需要知道最小边的原始边号。因此我可以用结构体啊。
using namespace std;
const int maxn = 100;
struct Node
{
int f,t,w,index;
}node[maxn];
int n,m;
int p[maxn];//p[i]=j表示i的爸爸是j
int ans;
bool com(Node a, Node b){return a.w < b.w;}
int Find(int x){return p[x]==x ? x : Find(p[x]);}
int main() {
cin >> n >> m;
for(int i=1; i<=m; i++){
cin >> node[i].f >> node[i].t >> node[i].w;
node[i].index = i;
}
for(int i=1; i<=n; i++) p[i] = i;
sort(node+1,node+1+m, com);
int edge,x,y;
for(int i=1; i<=m; i++){
edge = node[i].index;
x = Find(node[edge].f); y = Find(node[edge].t);
if(x!=y){
//ans += node[i].w;
ans += node[edge].w;
p[x] = y;
}
}
cout << ans << endl;
return 0;
}
/*
空间压缩后的算法。将一棵可能的单链树,变成2层树。
using namespace std;
const int maxn = 100;
struct Node
{
int f,t,w,index;
}node[maxn];
int n,m;
int p[maxn];//p[i]=j表示i的爸爸是j
int ans;
bool com(Node a, Node b){return a.w < b.w;}
//int Find(int x){return p[x]==x ? x : Find(p[x]);} //无忧化
int Find(int x) //优化后的。
{
int r = x;
while(p[r]!=r) r=p[r]; //这里表示寻找到了x的爸爸
int i=x,j;
while(i!=r){j=p[i];p[i]=r;i=j;} //这里是优化。
return r;
}
int main() {
cin >> n >> m;
for(int i=1; i<=m; i++){
cin >> node[i].f >> node[i].t >> node[i].w;
node[i].index = i;
}
for(int i=1; i<=n; i++) p[i] = i;
sort(node+1,node+1+m, com);
int edge,x,y;
for(int i=1; i<=m; i++){
edge = node[i].index;
x = Find(node[edge].f); y = Find(node[edge].t);
if(x!=y){
//ans += node[i].w;
ans += node[edge].w;
p[x] = y;
}
}
cout << ans << endl;
return 0;
}
*/
*/