算法合并共享至少2个元素

鉴于集列表集：算法合并共享至少2个元素

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]

什么最e合并所有共享至少两个元素的集合的方法很简单吗？我想这与连接组件问题很相似。因此，结果将是：

[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股1 S_1，和8 S_3，但不被合并，因为它们只共享在每一个元件）

朴素实施O（N^2），其中N是集合的数量，这对我们来说是行不通的。这需要对数百万套有效。

来源

2008-11-23 bajafresh4life

集合中的值的范围是多少？ – 2008-11-23 20:35:01

有没有整数？他们可以在一套内重复吗？ – EvilTeach 2008-11-23 20:38:08

集合中的值是整数，并且它们不在每个集合中重复 – bajafresh4life 2008-11-23 20:47:32

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）。带上一粒盐吧。

来源

2008-11-23 21:51:45 EvilTeach