algorithm - 从一组数据中将互斥数据添加到组中

Question

我有一组数据:

offerId  : Variants
  101:     (1)
  102:     (2,3)
  103:     (4)
  104:     (1,2,5)
  105:     (3)
  106:     (4,6)

我想在相互排斥的不同组中提供 offerId。像上面的数据一样，我会得到两个互斥的组:

   [101,102,104,105] corresponding to [(1),(2,3),(1,2,5),(3)]

   [103, 106] corresponding to  [(4),(4,6)]

我如何实现这一点，伪代码或逻辑任何东西都会受到赞赏。

P.S 我正在用 GO 语言编写代码。但我们将不胜感激以任何语言回答。

提前致谢。

Answer 1

你需要Disjoint-set数据结构。另一个名字——联合查找数据结构。

您可以在 Wiki 页面中看到伪代码，并在众多来源中看到真实的实现。 Arbitrary C# example .

在您的情况下，您还需要检查组(集？)的交集。如果两个组的交集不为空，则对这些组进行并集运算。