如何根据id与matched_id列计算生成bu_id列？

根据id和matched_id列生成bu_id列，规则如下：

1. 若matched_id非空，当前id与matched_id中所有id属于同一组，组内所有id的bu_id统一为组内最小的id（从输出示例可验证此逻辑，比如相互关联的0、7、8组最终bu_id都为0）
2. 若matched_id为空，bu_id等于当前id

输入数据：

+---+------------+
|id |matched_id  |
+---+------------+
|0  |7,8         |
|1  |            |
|2  |4           |
|3  |5,9         |
|4  |2           |
|5  |3,9         |
|6  |            |
|7  |0,8         |
|8  |0,7         |
|9  |3,5         |

期望输出：

+---+------------+-----+
|id |matched_id  |bu_id|
+---+------------+-----+
|0  |7,8         |0    |
|1  |            |1    |
|2  |4           |2    |
|3  |5,9         |3    |
|4  |2           |2    |
|5  |3,9         |3    |
|6  |            |6    |
|7  |0,8         |0    |
|8  |0,7         |0    |
|9  |3,5         |3    | 

核心逻辑：识别连通分量 #

这个问题本质是找出所有相互关联的id构成的连通分量——直接通过matched_id关联，或间接通过其他id关联的id属于同一分量。每个分量的bu_id取分量内最小的id即可满足需求。

高效实现：并查集（Union-Find）算法 #

并查集是处理连通分量问题的最优工具，具备高效的合并和查询操作，适合这类场景。

步骤说明

1. 初始化并查集：每个id的父节点初始化为自身，同时维护每个分量的最小id（初始为自身id）。
2. 合并关联id：遍历每一行数据，将当前id与matched_id中的所有id进行合并，合并时更新分量的最小id（取两个分量最小id的较小值）。
3. 生成结果：对每个id，查询其所在分量的最小id，作为该id的bu_id。

Python代码实现

class UnionFind:
    def __init__(self, max_id):
        self.parent = list(range(max_id + 1))
        self.min_id = list(range(max_id + 1))  # 存储每个分量的最小id
    
    def find(self, x):
        # 路径压缩，优化查询效率
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root != y_root:
            # 合并时保留较小的min_id作为分量的代表
            if self.min_id[x_root] < self.min_id[y_root]:
                self.parent[y_root] = x_root
            else:
                self.parent[x_root] = y_root

# 输入数据预处理：将matched_id转为整数列表
input_data = [
    (0, [7, 8]),
    (1, []),
    (2, [4]),
    (3, [5, 9]),
    (4, [2]),
    (5, [3, 9]),
    (6, []),
    (7, [0, 8]),
    (8, [0, 7]),
    (9, [3, 5])
]

# 初始化并查集
max_id = max(item[0] for item in input_data)
uf = UnionFind(max_id)

# 合并所有关联id
for current_id, matched_ids in input_data:
    for mid in matched_ids:
        uf.union(current_id, mid)

# 生成并打印结果
print("+---+------------+-----+")
print("|id |matched_id  |bu_id|")
print("+---+------------+-----+")
for current_id, matched_ids in input_data:
    matched_str = ",".join(map(str, matched_ids)) if matched_ids else "            "
    # 获取当前id所在分量的最小id
    bu_id = uf.min_id[uf.find(current_id)]
    print(f"|{current_id:2} |{matched_str:12} |{bu_id:4}|")
print("+---+------------+-----+")

替代思路：BFS/DFS遍历 #

如果不想用并查集，也可以用BFS或DFS遍历每个未处理的id，找出其所有关联id形成的分量，记录分量内最小id后统一赋值：

1. 维护一个已处理的id集合。
2. 遍历每个未处理的id，用BFS/DFS找出所有直接或间接关联的id，组成一个分量。
3. 取分量内最小id作为bu_id，给分量内所有id赋值，标记为已处理。
   这种方法逻辑直观，但数据量较大时，效率不如并查集。

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