库鲁斯卡尔算法+并查集解决最小生成树问题

#include<algorithm>
    typedef struct Line {
        int x, y, z;
    } Line;
// 顶点并查集
#define maxs 5000+5
#define maxl 500000+5
    int g[maxs];
    bool cmp(Line ls1, Line ls2) {
        return ls1.z < ls2.z;
    }
    int find(int x) {
        if (g[x] == x) {
            return x;
        } else return g[x] = find(g[x]);
    }
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */

    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        // write code here
        // write code here
        // 初始化 只能到达自己
        for (int i = 0; i <= n; i++) {
            g[i] = i;
        }
        Line ls[maxl];
        // 用来统计顶点数目 和代价
        int count = 0, minCost = 0;
        // 入参
        for (int i = 0; i < m; i++) {
            ls[i].x = cost[i][0];
            ls[i].y = cost[i][1];
            ls[i].z = cost[i][2];
        }
        sort(ls, ls+m, cmp);
        //先把最短的边放入
        g[ls[0].x] = ls[0].y;
        count+=2;
        minCost += ls[0].z;
            // 寻找可以放入并查集的最短边
            for (int j = 1; j < m; j++) {
                if(count==n) break;
                int x = find(ls[j].x), y = find(ls[j].y);
                if (x != y) {
                    g[x] = g[y];
                    count++;
                    minCost += ls[j].z;
                }
            }
        if (count == n) {
            return minCost;
        }
        return -1;
    }
};