Union查找算法的實現

我有一系列Key值對。每個密鑰都有2個值。鍵的值可能重合。最初，我從Key1開始，ValueKey1，ValueKey2存儲在一個集合（可能是數組）中。Union查找算法的實現

現在對於每個連續的Keyi，我檢查Valuei和Valuei + 1是否在集合中。如果其中任何一個在該集合中，則加入該集合。

否則，如果兩個KeyValues都出現在一個集合中，則丟棄該關鍵字。我如何使用C++實現這件事，我幾乎沒有想法，所以如果可能的話，代碼片段或提示將非常有幫助。

來源

2011-11-05 typedefcoder2

我不明白你的設置。首先你說你有「鍵值對」，然後你說「每個鍵有兩個值」。你有什麼基本的數據單位？你能澄清一下嗎？ –

我假設一個int值，對於那個int我有兩個關聯值int a，int b。現在我有很多這樣的對，並且必須使用聯合查找算法來查看是否有任何鍵值對重合... – typedefcoder2

這是否與圖形有關？ – AusCBloke

您是否正在使用或擁有'算法在C++'（Sedgewick，第3版）？

本書遇到的第一個問題是連接性問題（第7頁），其中有多種聯合查找（快速聯合，快速查找，加權等）算法的實現，它使用配對鍵。

這裏的快速查找版本：（這只是從書重新類型 - 未測試）

#include <iostream> 
const int N = 10000; 
int main() { 
    int i, p, q, id[N]; 
    for(i = 0; i < N; i++) id[i] = i; 
    while(cin >> p >> q) { 
     int t = id[p]; 
     if (t = id[q]) continue; 
     for (i = 0; i < N; i++) 
      if (id[i] == t) id[i] = id[q]; 
     cout << " " << p << " " << q << endl; 
    } 
}

只是不斷吐出未連接對（你很可能反轉爲得到你想要的）

這本書有一個非常詳細的說明它是如何工作的 - 我猜你現在有它。

來源

2011-11-05 23:10:21 Schnommus

不，先生..我沒有那本書。讓我試試你的解決方案。謝謝。 – typedefcoder2

Union查找算法的實現

回答

相關問題