将一组字符串对的数组转化为所有相连条目的数组。

Question

我有一个名字对的数组，如下：

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

我正在尝试编写一个方法，可以接受这个参数，并返回

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

在O(N^2)时间复杂度之内找到更好的解决方案。我的尝试如下：

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

但是这个解决方案在结果中有额外的团队，并且我能想到的每种解决方案都涉及非常糟糕的时间复杂度。如果您有任何想法，可以在不仅仅通过所有配对进行蛮力的情况下解决此问题，我会很愿意知道。

- Raynor

---

看起来你正在尝试将图分成连通分量。 我相信我在ruby图形库中看到了你需要的东西。 - Artem Ignatiev

一种不相交集合的数据结构可以在接近线性时间内解决您的问题：https://en.wikipedia.org/wiki/Disjoint-set_data_structure。我看到有很多Ruby宝石库实现了这个数据结构。 - John Ellmore

Answer 1

很幸运，不相交集是我最喜欢的数据结构。这里是一个快速而简单的实现：

pairs = [['alison', 'jason'], ['alison', 'chris'], ['john', 'bill'], ['bill', 'alex'], ['alex', 'jack'], ['steve', 'alex']]

parents = {}

pairs.each do |x, y|
  # each person starts as their own set, and their own representative
  parents[x] ||= x
  parents[y] ||= y

  # find representative of x set
  x_parent = parents[x]
  loop do
    break if parents[x_parent] == x_parent
    x_parent = parents[x_parent]
  end

  # find representative of y set
  y_parent = parents[y]
  loop do
    break if parents[y_parent] == y_parent
    y_parent = parents[y_parent]
  end

  # union by changing y's representative
  parents[y_parent] = x_parent
  # path compression to speed up later unions
  parents[x] = x_parent
  parents[y] = x_parent
end

# group by set representative (some paths might not be compressed)
groups = parents.each_key.group_by do |person|
  parent = parents[person]
  loop do
    break if parents[parent] == parent
    parent = parents[parent]
  end
  parent
end

p groups.values
[["alison", "jason", "chris"], ["john", "bill", "alex", "jack", "steve"]]

这大约是O(N+M)的复杂度，其中N是人数，M是配对数。请注意重复，例如查找集合代表。如果为查找定义一个适当的类，则算法看起来更加简洁。

此外，我的路径压缩不够理想，如果将压缩放在代表查找而不是并操作中，则可以进一步加快速度。

- Max