C语言中arr_arr_integer初始化求助（Roads Building算法题）

我正在做Codesignal平台上的Roads Building算法题，作为C语言新手，在初始化arr_arr_integer类型时遇到困难，找不到相同场景的示例，目前思路受阻，希望得到方向指引。

问题描述 #

已知王国的城市数量和现有道路，需找出需新建的道路使每对城市连通。返回的道路数组需按字典序排序，每条道路以[cityi, cityj]存储，且cityi < cityj。
示例：当cities=4、roads=[[0,1],[1,2],[2,0]]时，输出应为[[0,3],[1,3],[2,3]]。

// Arrays are already defined with this interface:
// typedef struct arr_##name {
//   int size;
//   type *arr;
// } arr_##name;
//
// arr_##name alloc_arr_##name(int len) {
//   arr_##name a = {len, len > 0 ? malloc(sizeof(type) * len) : NULL};
//   return a;
// }
//
//

void minmax(int x, int y, int *min, int *max){
    if(x > y){
        *max = x;
        *min = y;
    }else{
        *max = y;
        *min = x;
    }
}
bool checkForward(arr_arr_integer roads, int i, int j, int k){
    if(roads.arr[k].arr[0] != i && roads.arr[k].arr[1] != j){
        return false;
    }
    return true;
}
bool checkBack(arr_arr_integer roads, int i, int j, int k){
    if(roads.arr[k].arr[1] != i && roads.arr[k].arr[0] != j){
        return false;
    }
    return true;
}
bool checkconnection(arr_arr_integer roads, int i, int j, int k){
    return (checkForward(roads, i, j, k) && checkBack(roads, i, j, k));
}

arr_arr_integer solution(int cities, arr_arr_integer roads) {
    // init res array
    arr_arr_integer resArrArr;
    resArrArr.size=0;
     resArrArr.arr = malloc(cities * cities * sizeof(arr_integer));  // 
    // loop through cities
    for(int i=0; i<cities; i++){
          // for each city, loop through all other cities of higher index
          for(int j =i; j<cities; j++){
              //loop through roads & check for edge from i <-> j
              for(int k =0; k < roads.size; k++){
                  // if no connection is present add to res array
                if(!checkconnection(roads, i, j, k)){
                    int min, max;
                    minmax(i, j, &min, &max);
                    arr_integer edge;
                    edge.size = 2;
                    edge.arr[0] = min;
                    edge.arr[1] = max;
                    resArrArr.arr[resArrArr.size] = edge;
                    resArrArr.size ++;
                }
              }
          }
        
    }
    return resArrArr;
}

核心问题分析与解决方向 #

1. arr_arr_integer初始化的正确方式 #

根据题目给出的结构体定义和alloc_arr_##name函数模板，arr_arr_integer是存储arr_integer类型的数组。你当前的内存分配逻辑有两个关键问题：

• 直接手动初始化arr_integer时，edge.arr是未分配内存的野指针，直接赋值会触发内存访问错误。
• 应该使用题目提供的alloc_arr_integer函数来创建每个道路的arr_integer对象，而非手动构造。

修正示例：

// 正确创建一条道路的arr_integer
arr_integer edge = alloc_arr_integer(2);
edge.arr[0] = min;
edge.arr[1] = max;

2. 连通性检查逻辑错误 #

你的checkconnection函数逻辑完全错误：它要求第k条道路同时匹配(i,j)和(j,i)的双向条件，这永远无法成立，会导致结果数组中充斥大量重复且错误的道路。

正确的连通性检查逻辑：遍历所有现有道路，只要存在某条道路的两个端点是i和j（顺序无关），则说明二者已连通。封装后的函数如下：

bool isConnected(arr_arr_integer roads, int i, int j) {
    for (int k = 0; k < roads.size; k++) {
        int a = roads.arr[k].arr[0];
        int b = roads.arr[k].arr[1];
        if ((a == i && b == j) || (a == j && b == i)) {
            return true;
        }
    }
    return false;
}

3. 循环逻辑优化 #

当前三层循环会重复检查同一对城市多次，导致结果数组出现大量重复项。正确的循环逻辑应该是：

• 外层遍历i从0到cities-1
• 内层遍历j从i+1到cities-1（天然满足cityi < cityj，避免重复检查(i,j)和(j,i)）
• 对每对(i,j)调用一次isConnected，返回false时才添加到结果数组

4. 结果数组内存优化 #

你用cities * cities作为结果数组的最大容量，虽然安全但冗余。可提前计算所需道路数量：

int totalPossible = cities * (cities - 1) / 2; // 所有可能的道路数
int needed = totalPossible - roads.size; // 需要新建的道路数

然后用alloc_arr_arr_integer(needed)初始化结果数组，避免内存浪费。

修正后的代码框架示例 #

bool isConnected(arr_arr_integer roads, int i, int j) {
    for (int k = 0; k < roads.size; k++) {
        int a = roads.arr[k].arr[0];
        int b = roads.arr[k].arr[1];
        if ((a == i && b == j) || (a == j && b == i)) {
            return true;
        }
    }
    return false;
}

arr_arr_integer solution(int cities, arr_arr_integer roads) {
    int totalPossible = cities * (cities - 1) / 2;
    int needed = totalPossible - roads.size;
    
    arr_arr_integer resArrArr = alloc_arr_arr_integer(needed);
    int idx = 0;
    
    for (int i = 0; i < cities; i++) {
        for (int j = i + 1; j < cities; j++) {
            if (!isConnected(roads, i, j)) {
                arr_integer edge = alloc_arr_integer(2);
                edge.arr[0] = i;
                edge.arr[1] = j;
                resArrArr.arr[idx++] = edge;
            }
        }
    }
    
    return resArrArr;
}

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