寻求可将指定数对元素分入两个集合的函数实现方案

嘿，这个问题其实是个经典的二分图着色场景！你给出的每一组数对就相当于图里的一条边，两个数字是相连的节点，要求相连的节点必须分到不同的组（返回0或1）。咱们来一步步实现这个需求：

核心思路 #

把每个数字看作图的节点，数对看作节点间的连接边，我们需要给每个节点分配0或1的“颜色”，保证相邻节点颜色不同。这正是二分图的基本着色问题，用广度优先搜索（BFS）就能轻松解决。

具体实现步骤 #

1. 构建邻接表：先把所有数对转换成邻接表结构，方便快速找到每个数字的关联数字。
2. 遍历着色：用哈希表记录每个数字的分组，对未分组的数字启动BFS，给它和它的邻居交替分配0/1。
3. 封装查询函数：基于生成的分组映射，实现输入数字返回对应分组的函数。

代码示例（Python） #

from collections import deque

# 给定的数对列表
pairs = [(10, 20), (1, 31), (2, 32), (13, 23), (4, 14), (5, 25), (16, 26), (7, 17), (8, 28), (19, 29)]

# 第一步：构建邻接表
adjacency_list = {}
for num1, num2 in pairs:
    # 给num1添加邻居num2
    if num1 not in adjacency_list:
        adjacency_list[num1] = []
    adjacency_list[num1].append(num2)
    # 给num2添加邻居num1
    if num2 not in adjacency_list:
        adjacency_list[num2] = []
    adjacency_list[num2].append(num1)

# 第二步：生成分组映射
def create_group_mapping(adj):
    group_map = {}
    # 遍历所有节点，处理未分组的节点
    for node in adj:
        if node not in group_map:
            # 用队列实现BFS
            queue = deque([node])
            group_map[node] = 0  # 初始分组设为0
            while queue:
                current_node = queue.popleft()
                # 遍历当前节点的所有邻居
                for neighbor in adj[current_node]:
                    if neighbor not in group_map:
                        # 邻居分组设为当前节点的相反值
                        group_map[neighbor] = 1 - group_map[current_node]
                        queue.append(neighbor)
                    # 可选：检查是否存在冲突（比如奇数环导致无法二分）
                    elif group_map[neighbor] == group_map[current_node]:
                        raise ValueError("给定的数对存在冲突，无法完成二分分组")
    return group_map

# 生成分组字典
number_groups = create_group_mapping(adjacency_list)

# 第三步：查询函数
def get_group_number(num):
    # 如果输入的数字不在数对中，可返回-1或自行处理
    return number_groups.get(num, -1)

测试验证 #

比如调用：

• get_group_number(10) 返回 0，get_group_number(20) 返回 1
• get_group_number(1) 返回 0，get_group_number(31) 返回 1
  所有数对的两个元素都会返回不同的值，完全符合你的需求。

补充说明 #

如果后续新增数对，只要保证新增的数对不会形成奇数长度的环（比如1-2，2-3，3-1这样的三元环），这个方法依然有效。如果出现奇数环，会抛出异常提示冲突，这时就需要调整数对或者重新考虑分组规则啦。

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