如何在等效列表中找到最小的连接标签

Question

我有一个存储在标准向量中的数字列表。一些数字是其他数字的子代。这是一个例子

3, 4
3, 5
5, 6
7, 3
8, 9
8, 1
8, 2
9, 8

或作为图形：

1 2 3-4 5-6 7 8-9
|-------------|
  |-----------|
    |---|     
    |-------|

即有两个群集3,4,5,6,7和1,2,8,9。根号是集群的最小数目。这里是3和1。我想知道可以使用哪种算法来提取这样的列表：

3, 4
3, 5
3, 6
3, 7
1, 2
1, 8
1, 9

Answer 1

一种类似不相交集联合算法的算法可以为您提供帮助：