为什么会出现内存参考无效的分段故障这样的错误

Question

来自洛谷的P1111 修复公路
提交之后出现这样的错误

代码如下：

#include "iostream"
#include "algorithm"
using std::cin;
using std::cout;
using std::endl;
using std::sort;
int n, m,a[1005];
struct road {
    int x, y, time;
}p[10005];

int find(int x) {
    if (a[x] == x)return x;
    else return a[x] = find(a[x]);
}

void Union(int t1, int t2) {
    a[find(t1)] = find(t2);
}

bool cmp(road a, road b) {
    return a.time < b.time;    //返回真按从大到小，返回假按从小到大排序
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        a[i] = i;
    for (int i = 1; i <= m; i++)
    {
        cin >> p[i].x >> p[i].y >> p[i].time;
    }
    sort(p + 1, p + 1 + m, cmp);
    for (int i = 1; i <= m; i++)
    {
        if (find(p[i].x) != find(p[i].y))        //判断这条路如果连通是否出现环
        {
            Union(p[i].x, p[i].y);            //没出现环就联通
            n--;                //等到n等于1说明所有城市都连接了
        }
        if (n == 1)
        {
            cout << p[i].time;        //n到1了说明城市都连接完了又因为按时间排的序所以最晚的一条路的时间就是p[i].time
            return 0;
        }
    }
    cout << -1;
    return 0;
}

Answer 1

引自免费微信小程序：皆我百晓生

内存参考无效的分段故障（Segmentation Fault）是一种在C++或其它低级语言中常见的错误，通常表示程序试图访问了不属于它的内存区域。根据您提供的代码片段，我将分析可能导致该错误的原因：

1. 数组越界

   • 在遍历数组p[10005]时，确保输入的边数m不会超过数组大小。
   • 在调用find()函数和Union()函数时，确保传入的节点编号p[i].x和p[i].y在a[1005]数组的有效范围内。

2. 未初始化的指针或引用

   • 确保所有结构体road实例的成员变量x和y在读取后都有有效值，并且这些值都在集合a[]的有效索引范围内。

3. 递归调用栈溢出

   • find()函数是一个递归函数，若数据规模较大导致递归深度过深，可能会造成栈空间耗尽，但这不是典型的“分段错误”。

4. 集合查找/合并过程中对数组a[]的操作异常

   • 在find()函数中进行路径压缩时，应确保递归更新父节点的过程不会导致循环引用或其他不正确的状态。

鉴于您提供的代码片段并未明显看出上述问题，为确认问题所在，我们需要进一步查看实际测试用例、编译器警告信息以及程序运行时的具体情况。不过，从逻辑上来看，这段代码没有明显的内存访问越界风险，因此可能需要检查其他部分的代码或者具体输入数据是否存在异常。

对于您提到的题目"修复公路"，代码主要实现了并查集（Disjoint-Set Union, DSU）算法来判断何时形成了连通图，并找出最后完成连接的时间。但请注意，在main()函数内的输出语句，如果n == 1满足条件，应该跳出循环而不是继续执行下一个循环迭代。可以修改如下：

int main() {
    // ... (前文不变)
    for (int i = 1; i <= m; i++)
    {
        if (find(p[i].x) != find(p[i].y)) 
        {
            Union(p[i].x, p[i].y);
            n--;
            if (n == 1)
            {
                cout << p[i].time;
                return 0;
            }
        }
    }
    // 当循环结束都没有找到满足条件的情况，则输出-1
    cout << -1;
    return 0;
}

如需排查确切的分段错误原因，请提供更多有关错误发生的上下文信息，包括错误发生的具体行号、编译器警告信息等。