GFG练习中使用Kruskal算法求MST出现段错误，求代码bug排查

核心错误点 #

• 全局并查集数组pr、sz未初始化大小：spanningTree函数中直接调用mset(i)对pr[i]、sz[i]赋值时，两个vector是空的，数组越界访问直接触发段错误。
• 全局边数组ans未清空：多次调用spanningTree函数时，上一次的边数据会残留，导致边集合错误，即使单次运行也可能因为测试用例多次调用函数触发异常。
• 自定义比较函数com未使用：代码中定义了降序比较的com函数，但调用sort时没有传入，虽然Kruskal需要升序排序，默认行为刚好符合要求，但冗余代码容易引发后续修改失误。
• 并查集合并逻辑冗余：uset函数中pr[v] = pr[u]可直接写为pr[v] = u，因为u已经是根节点，pr[u]等于自身，虽然不影响运行，但不符合常规写法。
• 边重复存储：遍历邻接表时无向边会被添加两次，虽然不影响最终计算结果，但会增加排序和遍历的时间开销。

修复后代码 #

#include <vector>
#include <algorithm>
using namespace std;

vector<int> pr;
vector<int> sz;

void mset(int u)
{
    pr[u] = u ;
    sz[u] = 1;
}

int fset(int u)
{
    if(pr[u] == u)
        return u;
    return pr[u] = fset(pr[u]);
}

void uset(int u , int v)
{
    u = fset(u);
    v = fset(v);
    if(u != v)
    {
        if(sz[u] < sz[v])
            swap(u , v);
        sz[u] += sz[v];
        pr[v] = u; // 修正冗余写法
    }
}

int spanningTree(int V, vector<vector<int>> adj[])
{
    // 初始化并查集数组，解决越界问题
    pr.resize(V);
    sz.resize(V);
    for(int i = 0 ; i < V ; i++)
    {
        mset(i);
    }
    int cost = 0;
    // ans改为局部变量，避免全局残留问题
    vector<vector<int>> ans;
    for(int i = 0 ; i < V ;i++)
    {
        for(auto j : adj[i] )
        {
            ans.push_back( {j[1],j[0],i} );
        }
    }
    // 默认升序排序符合Kruskal算法要求
    sort(ans.begin() , ans.end());
    for(auto i : ans )
    {
        int w = i[0];
        int u = i[1];
        int v = i[2];
        u = fset(u);
        v = fset(v);
        if(v == u)
        {
            continue ;
        }
        cost += w;
        uset(u , v);
    }
    return cost ;
}

内容的提问来源于stack exchange，提问作者B G