又给 ChatGPT 出了道算法题。好嘛，难不住它。

[sillydaddy]

题目是实际工作中拿出来的，稍作简化了一下。可惜问的时候我已经写完了，后悔没早点问它。

对于它的解题能力，一些人可能仍然不屑一顾。但我是服了。首先，是它表现出的理解能力，这可是自然语言啊。然后，架不住它快啊。

我：

考你一个算法题。现在有 1 个已知的接口，能根据 cellid 返回与之相邻的多个 cellid ，现在给定一个 cellid 的数组，要求实现一个接口，返回连通的各组 cell 。即每组内的各个 cell 是互相连通的。如果你觉得不明白连通的具体含义，我可以再详细解释。

NewBing：

你好，这是 Bing 。我可以尝试回答你的算法题，但是我不保证正确性。根据百度知道 1 ，连通的含义是“接连而又相通”，也就是说两个 cell 之间有路径可以互相到达。如果我理解得没错的话，你要求的接口就是把给定的 cellid 数组分成若干个子数组，使得每个子数组内的 cell 都是连通的，而不同子数组之间的 cell 都是不连通的。这样对吗？

我：

我感觉你理解了这个题目。能给出具体的代码吗？ 已知的接口是 std::vector<int> get_neighbors(int cellid)。请实现接口 std::vector<std::vector<int>> group_all_cells(std::vector<int>)

NewBing：
好的，我会尽力给出一个可能的代码实现，但是我不保证它是最优的或者没有错误的。我的思路是使用深度优先搜索（ DFS ）来遍历给定的 cellid 数组，对每个 cellid ，如果它还没有被访问过，就把它和它的所有连通的邻居放到一个新的子数组中，并标记为已访问。这样重复直到所有 cellid 都被访问过。以下是我生成的代码：

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

// 已知接口
vector<int> get_neighbors(int cellid);

// 待实现接口
vector<vector<int>> group_all_cells(vector<int> cellids) {
  // 用一个集合来存储已经访问过的 cellid
  unordered_set<int> visited;
  // 用一个向量来存储结果
  vector<vector<int>> result;
  // 遍历给定的 cellid 数组
  for (int cellid : cellids) {
    // 如果当前 cellid 还没有被访问过
    if (visited.find(cellid) == visited.end()) {
      // 创建一个新的子数组，并把当前 cellid 放进去
      vector<int> group;
      group.push_back(cellid);
      // 标记当前 cellid 为已访问
      visited.insert(cellid);
      // 使用 DFS 来找到所有与当前 cellid 连通的邻居，并放到同一个子数组中
      dfs(cellid, visited, group);
      // 把子数组加入结果中
      result.push_back(group);
    }
  }
  return result;
}

// 辅助函数，使用 DFS 来找到所有与给定 cellid 连通的邻居，并放到同一个子数组中
void dfs(int cellid, unordered_set<int>& visited, vector<int>& group) {
  // 获取当前 cellid 的所有邻居
  vector<int> neighbors = get_neighbors(cellid);
  // 遍历邻居
  for (int neighbor : neighbors) {
    // 如果邻居还没有被访问过
    if (visited.find(neighbor) == visited.end()) {
      // 把邻居加入子数组中
      group.push_back(neighbor);
      // 标记邻居为已访问
      visited.insert(neighbor);
      // 对邻居递归调用 DFS 函数，继续寻找连通的邻居
      dfs(neighbor, visited, group);
    }
  }
}

我：

很不错。如果 get_neighbors 接口返回的 cell 不一定在 group_all_cells 的输入参数中呢？也就是说 get_neighbors 接口得到的邻居，可能不再待分组的所有 cells 里面。请针对这种情况修改一下代码吧。如果有不清楚的地方可以询问我。

NewBing：

好的，我明白你的意思。如果 get_neighbors 接口返回的 cell 不一定在 group_all_cells 的输入参数中，那么我们就需要额外判断一下当前 cell 是否在输入参数中，如果不在，就跳过它。为了方便判断，我们可以先把输入参数转换成一个集合。以下是我修改后的代码：

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

// 已知接口
vector<int> get_neighbors(int cellid);

// 待实现接口
vector<vector<int>> group_all_cells(vector<int> cellids) {
  // 用一个集合来存储已经访问过的 cellid
  unordered_set<int> visited;
  // 用一个向量来存储结果
  vector<vector<int>> result;
  // 把输入参数转换成一个集合，方便判断 cell 是否在其中
  unordered_set<int> cellset(cellids.begin(), cellids.end());
  // 遍历给定的 cellid 数组
  for (int cellid : cellids) {
    // 如果当前 cellid 还没有被访问过
    if (visited.find(cellid) == visited.end()) {
      // 创建一个新的子数组，并把当前 cellid 放进去
      vector<int> group;
      group.push_back(cellid);
      // 标记当前 cellid 为已访问
      visited.insert(cellid);
      // 使用 DFS 来找到所有与当前 cellid 连通且在输入参数中的邻居，并放到同一个子数组中
      dfs(cellid, visited, group, cellset);
      // 把子数组加入结果中
      result.push_back(group);
    }
  }
  return result;
}

// 辅助函数，使用 DFS 来找到所有与给定 cellid 连通且在给定集合中的邻居，并放到同一个子数组中
void dfs(int cellid, unordered_set<int>& visited, vector<int>& group, unordered_set<int>& cellset) {
  // 获取当前 cellid 的所有邻居
  vector<int> neighbors = get_neighbors(cellid);
  // 遍历邻居
  for (int neighbor : neighbors) {
    // 如果邻居还没有被访问过且在给定集合中（即是待分组的）
    if (visited.find(neighbor) == visited.end() && cellset.find(neighbor) != cellset.end()) {
      // 把邻居加入子数组中
      group.push_back(neighbor);
      // 标记邻居为已访问
      visited.insert(neighbor);
      // 对邻居递归调用 DFS 函数，继续寻找连通且待分组的邻居
      dfs(neighbor, visited, group, cellset);
    }
  }
}