如何基于图与DFS/BFS实现O(n)时间的人员事件归属关系查询

当前判定场景的基础为：仅设置两个可供参与的独立活动事件，需要对任意两个待比较人员做关系判定：

• 能明确判定两人参加同一事件或不同事件的，直接输出对应结论
• 存在多种合理可能性、无法得出唯一确定结论的，判定为现有信息不足

输入为三类条目组成的列表，每条格式为「条目类型 + 两个以唯一数字编号标识的人员」：

• different_connection：两个人员分属不同事件
• same_connection：两个人员属于同一事件（原文记录的sane_connection为该类型的笔误）
• find_connection：需要返回判定结果的待查询人员对

输出结果的判定规则：

• 可明确同一事件：返回same_connection
• 可明确不同事件：返回different_connection
• 信息不足无法得出确定结论：返回unknown_connection

示例输入如下：

find_connections(
    ['different_connection 3 5',
     'same_connection 5 6',
     'different_connection 1 2',
     'same_connection 2 5',
     'different_connection 9 8'
     'find_connection 1 3',
     'find_connection 1 5',
     'find_connection 2 5',
     'find_connection 6 8'])

注：示例输入中different_connection 9 8行末缺失列表分隔逗号，为原输入笔误

对应示例输出如下：

['same_connection','different_connection','same_connection', 'unknown_connection']

• 基础约束：人员总数为有限有界值，每次仅开展两人关系比较
• 性能目标：实现*最坏时间复杂度为O(n)*的解法，其中n为输入信息列表的元素总数
• 现有可用方案的局限：目前已能通过邻接表+DFS循环遍历的方式实现正确逻辑，但该方案在查询环节的最坏时间复杂度为O(n²)，无法达到性能要求
• 当前进展：已掌握基于图结构推导正确结果的逻辑，可手动绘制对应关系图完成判定，但尚未找到满足O(n)时间复杂度要求的实现路径，也不确定图结构相关的通用工具是否可支撑达成该性能目标

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