算法合併共享至少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