最小生成树是数据结构中一个经典的问题，一次在刷题的过程中遇到了这类的问题，那时候遇到这类问题就很迷茫。建立最小生成树有两种方法，一种是以点建树，每次都选择最近的点，即prim算法；另一种是以边建树，每次都选择最短的边，即kruskal算法，prim算法可以不借助并查集就可建树，但是当我们用kruskal算法是就需要用到并查集了。

并查集的的作用

并查集的作用是判断两个顶点之间是否是连通状态。

并查集的思想

初始有N个各不相同的集合，输入其中的一些边，使其中的顶点相互连通，直至所有的顶点都相互连通，成为一个集合，若他们的权值之和最小，则说明这是一颗最小生成树。 还是用通俗的语言来说吧。亲戚关系，现在有三个原本互相不认识的人聚到了一起，他们分别是A,B,C；随着三人之间的更加熟悉，A和B是亲戚关系（即A和B之间是连通的，他们合并到一个集合），B和C之间也是亲戚关系，所以A和C之间也是亲戚，所以A、B、C都是亲戚关系，即他们都是连通的（三者是同一个集合），这个时候我们怎么知道他们三个是亲戚关系？只需要从他们之中找出一个代表，A二大爷和B大表叔是同一个人X，这个时候两个人就以X为枢纽建立了亲戚关系，为了方便，每次把最后一个并入到集合中的人，当做枢纽X。

并查集的代码

#include<iostream>
using namespace std;
const int Max=1e5+2;//假设结点的最大数目不超过Max
int fa[Max];
void build(int n)//初始化,n个人都在不同的集合
{
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    return ;
}
int Find(int m)//这个函数作用是寻找他们枢纽X,一定要用int
{
    return fa[m]==m?m:fa[m]=Find(fa[m]);
}
bool che(int x,int y)//判断两个点是否属于同一个集合，即亲戚关系
{
    return Find(x)==Find(y);
}
void mer(int x,int y)//如果不是亲戚关系就把他们合并到一起
{
    if(!che(x,y)){
        fa[fa[x]]=fa[y];
    }
    return ;
}
int main()
{
    int n;
    cin >> n;
    build(n);
    int p;//假设要输入p条边
    cin >> p;
    while(p--){
        int x,y;
        cin >> x >> y;
        mer(x,y);
    }
    int q;//检查两个点是否已经连通
    cin >> q;
    while(q--){
        int x,y;
        cin >> x >> y;
        if(che(x,y)){
            cout << "Yse" << endl;
        }
        else{
            cout << "No" << endl;
        }
    }
    return 0;
}

如果想要做最小生成树，只要将输入的边保存下来，然后排序，一个个输入，直到五个结点都在同一个集合中，对上面程序做简要的添加删除即可。