本文共 815 字，大约阅读时间需要 2 分钟。

题目描述

题解：题目中的vector中是由多个列表组成，每个列表只有三个元素，分别表示边的起点，边的终点以及边的权重信息。

• 将所有边的全权重信息排序，时间复杂度为O(mlog_m) m:边数
• 枚举每条边a,b，及其权重w，如果a,b边不连通则加入集合

具体算法执行过程可以看该博客的详细解释https://blog.csdn.net/qq_41754350/article/details/81460643

在实现该算法时，使用到了并查集的find函数，该函数用于查找节点的树根节点，因此需要初始化一个 p 数组，表示节点的父亲节点，初始 p 数组中的值是节点本身。在查找的过程中如果发现父亲节点与 x 不相同那么一直向上寻找，为什么这样做，原因在于 树根节点与自己本身是相同的，如果不同表示该节点是父亲节点的子节点，需要继续向上找。实现find函数用的是递归的方式。

const int N=200010;class Solution {   public:    int p[N];    struct Edges    {           int a,b,w;        bool operator < (const Edges &W) const        {               return w