如何在等价列表中找到最小连通标签

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

一个类似不相交集合联合算法的算法可以帮助你：

• 初始化每个不相交的子集，每个子集恰好有一个数字，并且N i(r(i))的根是每个边的(u, v)，你可以赋值：

    t = min(r(u), r(v))
    r(u) = t
    r(v) = t

对于每个i，您可以使用i != r(i)写出