用于合并共享至少2个元素的集合的算法

Question

给出一组集合:

• S_1:[1,2,3,4]
• S_2:[3,4,5,6,7]
• S_3:[8,9,10,11]
• S_4:[1,8,12,13]
• S_5:[6,7,14,15,16,17]

合并至少共享2个元素的所有集合的最有效方法是什么？我想这类似于连接组件问题.结果将是:

• [1,2,3,4,5,6,7,14,15,16,17](S_1 UNION S_2 UNION S_5)
• [8,9,10,11]
• [1,8,12,13](S_4与S_1共享1,与S_3共享8,但未合并,因为它们只共享一个元素)

天真的实现是O(N ^ 2),其中N是集合的数量,这对我们来说是行不通的.这需要对数百万套有效.

Answer 1

Let there be a list of many Sets named (S)

Perform a pass through all elements of S, to determine the range (LOW .. HIGH).

Create an array of pointer to Set, of dimensions (LOW, HIGH), named (M).

do
    Init all elements of M to NULL.   

    Iterate though S, processing them one Set at a time, named (Si).

        Permutate all ordered pairs in Si. (P1, P2) where P1 <= P2.
        For each pair examine M(P1, P2)
            if M(P1, P2) is NULL
                Continue with the next pair.
            otherwise
                Merge Si, into the Set pointed to by, M(P1, P2).
                Remove Si from S, as it has been merged.
                Move on to processing Set S(i + 1)

        If Si was not merged, 
            Permutate again through Si
            For each pair, make M(P1, P2) point to Si.

while At least one set was merged during the pass.

我的头脑在说这是关于订单（2N ln N）。对此持保留态度。