前言
最小生成树是指在一个无向图内，找出一棵树，使得各个结点之间能够互相到达，且总路径长度最短。

程序设计思路
最小生成树主要有两种思路——Kruskal和Prim，两者的时间复杂度为On2和On3，限于篇幅原因，故进行两者的讲解，只提供Kruskal的代码。
首先讲时间复杂度较高的Prim算法（有点像dijkstra）：在图中先确定一个点，将该点加入队列，之后每次循环在与队列中的所有点连接的边中找出最短边（不得与之前已经在队列中的点相连），直到所有的点都被加入队列。
Kruskal是一种基于贪心的算法：每次在所有的边中找出最短边，判断其两端有没有与之前已经相连的点重复，直到所有点之间都已连接。因此，Kruskal需要进行排序操作。

代码实现

这里只放Kruskal的代码：

#include <bits/stdc++.h>
struct tree{//存边，x、y分别代表两个端点，z为边权
    int x,y,z;
}tr[200005];

int n,m,iq,aq,sb=0,bin[5005],ans=0;//n、m如题意，iq、aq分别临时存放路径，sb用于计数（只拿n-1条边），bin存放每个点的路径，ans累加长度

int find(int a){//由于Kruskal基于树进行，可以使用路径压缩，详见并查集那篇文章
    int x=a;
    if(bin[x]!=x) return bin[x]=find(bin[x]);
    else return x;
}

bool cmp(tree a,tree b){//sort升序
    return a.z<b.z;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){//读入
        scanf("%d%d%d",&tr[i].x,&tr[i].y,&tr[i].z);
        bin[tr[i].x]=tr[i].x;
        bin[tr[i].y]=tr[i].y;
    }
    sort(tr+1,tr+m+1,cmp);//升序排序
    for(int i=1;i<=m;i++){//遍历每条边
        iq=find(tr[i].x);//找当前边的x是否连入图中
        aq=find(tr[i].y);//找当前边的y是否连入图中
        if(iq==aq) continue;//当两者祖先相同时，直接跳过防止成环
        ans+=tr[i].z;//累加
        sb++;//计次
        bin[aq]=iq;//修改路径
        if(sb==n-1) break;//当要取的边数量足够时，退出循环
    }
    for(int i=1;i<n;i++) if(find(i)!=find(i+1)){//判断每个点的祖先是否相同
        printf("orz");
        return 0;
    }
    printf("%d",ans);
    return 0;
}

这里需要注意的是，由于我们已经完成了排序，故不需要在之后判断大小。

结语
本文中讲了Kruskal的思路及代码，并融入了并查集的知识。我是faryou，再见！

前言
图论是算法中的一个重要内容，图的范围很广，包括二叉树、树、图等。今天我们来学习树的重要内容——并查集。

程序设计思路
并查集是一个森林（由一棵或多棵树组成的集）。我们可以利用其特性进行一些操作。
在并查集中，最重要的操作便是并和查。
并是指将两棵树合并为一棵。这很好进行，因为并查集里的每个数都有一个指针指向自己的父亲。
查找也不难，只需要一个递归程序，不断查找父亲的父亲，最后找到最老的祖先再返回（注意：并查集中最老的祖先的祖先是其自身）。
比较重要的是一个优化方案——路径压缩。由于查找是递归调用，故当要找的祖先过于遥远时，我们可以使用路径压缩，将一棵树中的全部非根节点的祖先直接设置为最老的祖先。路径压缩通常在执行查找命令时进行。

代码实现
下面通过并查集的模板题讲解其用法：

这题要求我们模拟并查集的操作，直接上代码：

#include <bits/stdc++.h>
using namespace std;

int n,m,z[200005],x[200005],y[200005],bin[10005];//z、x、y如题意，bin为并查集中每个数的祖先（父亲）

int find(int a){//查找操作
    int x=a;
    if(bin[x]!=x) return bin[x]=find(bin[x]);//在查找的过程中路径压缩
    else return x;//当查到某个数的祖先是它自己时，说明找到了祖先，开始返回
}
void join(int b,int c){//并操作
    if(find(b)!=find(c)) bin[find(b)]=find(c);
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) bin[i]=i;
    for(int i=1;i<=m;i++) scanf("%d%d%d",&z[i],&x[i],&y[i]);
    for(int i=1;i<=m;i++){
        if(z[i]==1) join(x[i],y[i]);
        else{
            if(find(x[i])==find(y[i])) printf("Y\n");
            else printf("N\n");
        }
    }
    return 0;
}

这样，我们就较好的模拟了一个并查集。

结语
并查集是图论中较为简单的一科，只需要记下并、查两个操作就可以解决相关问题。我是faryou，再见！