使用并查集判断迷宫连通性时大文件触发Invalid Read段错误如何解决

核心原因 #

程序触发Invalid Read和大文件下段错误的核心原因是内存越界访问：小文件场景下越界访问的是未被其他逻辑占用的合法内存，不会触发操作系统的内存保护中断；大文件场景下越界访问到不可读/已被占用的内存，直接触发段错误。

具体错误点 #

• 并查集数组索引越界：你初始化id、sz数组时申请了长度为N的内存，合法下标范围是0 ~ N-1，但你计算单元格编号的逻辑生成的最大值超过了这个范围：
  1. 矩阵遍历阶段，你计算单元格编号用了(r-1)*col + c，r最大为row、c最大为col，最终得到的最大编号为row*col，如果N=row*col，该值刚好比合法最大下标大1，直接越界。
  2. 最终连通性校验阶段，你计算单元格编号用了(dados[2]-1+1)*col+dados[3]+1，化简后为dados[2]*col + dados[3] +1，比合法索引值大更多，越界程度更严重。
• 路径压缩逻辑存在未初始化变量访问：cwqunion函数中路径压缩的循环里，你先执行了i = x再给x赋值，第一次循环时x是未初始化的随机值，随机值落在合法地址范围时程序正常运行，落在非法范围时直接触发Invalid Read。

修复方案 #

1. 统一单元格编号规则：所有单元格编号统一从0开始计算，修正遍历阶段的编号逻辑：

int cur_id = (r-1)*col + (c-1);
if(c!=col && tabela[r-1][c] == 0) {
    int right_id = (r-1)*col + c;
    cwqunion(cur_id, right_id, id, sz);
}
if(r!=row && tabela[r][c-1] == 0) {
    int down_id = r*col + (c-1);
    cwqunion(cur_id, down_id, id, sz);
}

2. 修正连通性校验阶段的编号计算逻辑（假设dados中存储的单元格行列是从1开始计数的）：

int a_id = (dados[2]-1)*col + (dados[3]-1);
int b_id = (dados[6]-1)*col + (dados[7]-1);
for (i = a_id; i != id[i]; i = id[i]);
for (j = b_id; j != id[j]; j = id[j]);

3. 修复cwqunion函数路径压缩的变量顺序问题：

for (i = p; i != id[i]; ) {
    x = id[i];
    id[i] = t;
    i = x;
}
for (j = q; j != id[j]; ) {
    x = id[j];
    id[j] = t;
    j = x;
}

4. 确认N的取值：保证N = row * col，避免数组长度不足导致越界。

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