相机网格排序：求解可通信同网格的相机数量

看起来你卡在了合并连通相机组的环节——这本质是个典型的图的连通分量计数问题，咱们一步步来把它理顺：

首先明确问题核心：你已经得到了所有两两直接连通的相机对（距离平方≤r²），现在需要把这些对里有共同相机的组合并，最终统计有多少个独立的连通网格（也就是图论里的「连通分量」）。

最优解法：用并查集（Union-Find）高效处理连通合并 #

并查集是专门解决这类「动态连通性」问题的数据结构，它能快速合并两个连通集合，并且查询某个节点属于哪个集合，效率远高于手动列表合并。

步骤拆解 #

1. 给相机分配唯一标识：把每个坐标元组映射成整数ID（元组直接当键也可以，但整数操作更高效）。
2. 初始化并查集：每个相机初始时属于自己的独立集合。
3. 合并连通对：遍历你得到的lis列表，把每一对连通的相机合并到同一个集合里。
4. 统计连通分量：遍历所有相机，统计有多少个不同的「根节点」，每个根节点对应一个独立的连通网格。

代码实现示例 #

def count_connected_cameras(lis):
    # 第一步：收集所有相机，生成ID映射
    all_cameras = set()
    for pair in lis:
        all_cameras.add(pair[0])
        all_cameras.add(pair[1])
    camera_to_id = {cam: idx for idx, cam in enumerate(all_cameras)}
    total_cameras = len(all_cameras)
    
    # 初始化并查集父节点数组
    parent = list(range(total_cameras))
    
    # 查找根节点，带路径压缩优化
    def find(node):
        while parent[node] != node:
            parent[node] = parent[parent[node]]  # 路径压缩，加快后续查询
            node = parent[node]
        return node
    
    # 合并两个节点所在的集合
    def union(node1, node2):
        root1 = find(node1)
        root2 = find(node2)
        if root1 != root2:
            parent[root2] = root1
    
    # 遍历所有连通对，执行合并
    for cam_a, cam_b in lis:
        id_a = camera_to_id[cam_a]
        id_b = camera_to_id[cam_b]
        union(id_a, id_b)
    
    # 统计不同的根节点数量，即连通分量数
    unique_roots = set()
    for idx in range(total_cameras):
        unique_roots.add(find(idx))
    return len(unique_roots)

# 测试你的示例数据
lis = [ [(3,4),(5,6)] ,[(2,4),(5,9)], [(1,4),(5,6)] ]
print(count_connected_cameras(lis))  # 输出：2
# 解释：(3,4)、(5,6)、(1,4)是一个连通组；(2,4)、(5,9)是另一个独立组

备选思路：DFS遍历标记连通分量 #

如果你不想用并查集，也可以用深度优先搜索（DFS）来逐个遍历未标记的相机，找出所有和它连通的相机，标记后计数：

def count_connected_cameras_dfs(lis):
    # 构建邻接表：每个相机对应的直接连通相机列表
    adjacency = {}
    for cam1, cam2 in lis:
        adjacency.setdefault(cam1, []).append(cam2)
        adjacency.setdefault(cam2, []).append(cam1)
    
    visited = set()
    component_count = 0
    
    # DFS遍历单个连通分量
    def traverse(cam):
        stack = [cam]
        visited.add(cam)
        while stack:
            current = stack.pop()
            for neighbor in adjacency.get(current, []):
                if neighbor not in visited:
                    visited.add(neighbor)
                    stack.append(neighbor)
    
    # 遍历所有相机，处理未访问的节点
    all_cameras = set()
    for pair in lis:
        all_cameras.update(pair)
    
    for cam in all_cameras:
        if cam not in visited:
            traverse(cam)
            component_count += 1
    return component_count

# 测试示例
lis = [ [(3,4),(5,6)] ,[(2,4),(5,9)], [(1,4),(5,6)] ]
print(count_connected_cameras_dfs(lis))  # 输出：2

为什么手动合并列表容易卡壳？ #

你之前尝试直接合并有共同元组的列表，这种方法在数据量小的时候能凑合用，但当连通关系复杂时（比如A连B、B连C、C连D），需要多次迭代检查列表间的交集，不仅效率低，还容易遗漏嵌套的连通关系。而并查集或DFS的方法是从「节点连通性」的本质出发，能更系统地处理所有情况。

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