如何以优于O(N²)的时间复杂度找出字符串对数组的连通分量

我需要编写一个方法，将形如以下的字符串对数组：

[ ['alison', 'jason'], ['alison', 'chris'], ['john', 'bill'], ['bill', 'alex'], ['alex', 'jack'] ]

转换为连通元素的分组数组，期望输出为：

[ ['alison', 'jason', 'chris'], ['john', 'bill', 'alex', 'jack'] ]

要求时间复杂度优于O(N²)。我自己尝试了一段Ruby代码，但该方案会生成多余的分组，目前也想不出其他非暴力的高效解决方案。

我编写的Ruby代码如下：

def teams(arr)
  pair_hash = {}
  arr.each do |pair|
    if pair_hash[pair[0]].nil?
      pair_hash[pair[0]] = [pair[1]]
    else
      pair_hash[pair[0]].push(pair[1])
    end
  end
  teams = []
  pair_hash.map do |leader, team|
    teams.push(find_teammates(pair_hash, leader, team))
  end
  teams
end

def find_teammates(hash, leader, team)
  result = [leader]
  team.each do |member|
    if hash[member].nil?
      result += [member]
    else
      result += find_teammates(hash, member, hash[member])
    end
  end
  result
end

这个问题本质是寻找无向图中的连通分量，并查集（Union-Find）是解决这类问题的最优选择之一，它的时间复杂度为O(Nα(N))——其中α是阿克曼函数的反函数，增长速度极慢，实际工程中可以视为常数，完全符合你对“优于O(N²)”的要求。

下面是用Ruby实现的完整并查集方案：

class UnionFind
  def initialize
    @parent = {}  # 记录每个节点的父节点
    @rank = {}    # 记录每个树的秩（高度），用于平衡合并
  end

  # 查找节点的根节点，同时执行路径压缩优化
  def find(x)
    # 如果当前节点不是根节点，递归查找根，并把当前节点直接挂载到根节点下
    @parent[x] = find(@parent[x]) if @parent[x] != x
    @parent[x]
  end

  # 合并两个节点所在的连通分量
  def union(x, y)
    # 初始化节点：如果节点还没在集合中，把自身设为父节点
    @parent[x] = x unless @parent.key?(x)
    @parent[y] = y unless @parent.key?(y)
    
    root_x = find(x)
    root_y = find(y)
    
    return if root_x == root_y  # 两个节点已经在同一集合，无需合并
    
    # 按秩合并：把秩小的树合并到秩大的树下，避免树过度增高
    if (@rank[root_x] ||= 0) > (@rank[root_y] ||= 0)
      @parent[root_y] = root_x
    else
      @parent[root_x] = root_y
      @rank[root_y] += 1 if @rank[root_x] == @rank[root_y]
    end
  end

  # 生成最终的分组结果
  def groups
    groups = Hash.new { |h, k| h[k] = [] }
    @parent.each_key do |node|
      # 找到每个节点的根，把节点归入对应根的分组
      groups[find(node)] << node
    end
    groups.values
  end
end

# 调用并查集的teams方法
def teams(arr)
  uf = UnionFind.new
  arr.each { |x, y| uf.union(x, y) }
  uf.groups
end

# 测试示例
input = [ ['alison', 'jason'], ['alison', 'chris'], ['john', 'bill'], ['bill', 'alex'], ['alex', 'jack'] ]
p teams(input)
# 输出：[["alison", "jason", "chris"], ["john", "bill", "alex", "jack"]]

方案优势说明 #

• 路径压缩：在find操作时，会将节点直接连接到根节点，后续查找操作的耗时会大幅降低。
• 按秩合并：合并时优先将矮树合并到高树下，保持树的平衡，避免出现极端的链式结构，保证操作的高效性。

原代码的问题分析 #

你的原方案本质是深度优先遍历，但没有记录已访问的节点，导致同一个连通分量会被多次处理（比如如果jason也作为键存在于pair_hash中，会再次生成相同的分组），最终产生多余的结果。而并查集通过记录每个节点的根节点，天然避免了重复处理，最后只需将同一根节点下的节点归为一组即可。

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