연결이 끊긴 집합으로 연결된 집합

Question

연결 집합으로 연결이 끊긴 집합에 대한 정보를 누군가에게 알려줄 수 있습니까? 이것에 대한 코드를 찾을 수 없습니다. 언어 C++

Answer 1

이 페이지의 정보는 Wikipedia입니다. 물론이 정보는 의사 코드로 작성되지만 번역하기가 어렵지는 않습니다.

Answer 2

부스트의 구현은 http://www.boost.org/doc/libs/1_39_0/libs/disjoint_sets/disjoint_sets.html입니다. 이것이 당신이 찾고있는 것 같아요.

Answer 3

누구나 여전히 관심이 있다면 나는 이것을 작성했습니다. CLRS를 구현했습니다.

/****************************************************************** 
* PROGRAM: Implementation of Linked-list representation of disjoi-* 
*   nted sets in C++ without weighted union optimization. * 
*   makeset, find takes O(1), Union takes O(n). Testing * 
*   code is in the main method.       * 
* AUTHOR: Bo Tian (bt288 at cam.ac.uk) drop me an email if you * 
*   have any questions.         * 
* LICENSE: Creative Commons Attribution 3.0 Unported    * 
*   http://creativecommons.org/licenses/by/3.0/   * 
*******************************************************************/ 


#include <iostream> 
using namespace std; 

long NodeAddress[10] = {0}; 
int n=0; 

template<class T> class ListSet { 
private: 
    struct Item; 
    struct node { 
     T val; 
     node *next; 
     Item *itemPtr; 
    }; 
    struct Item { 
     node *hd, *tl; 
    }; 

public: 
    ListSet() { } 
    long makeset(T a); 
    long find (long a); 
    void Union (long s1, long s2); 
}; 

template<class T> long ListSet<T>::makeset (T a) { 
    Item *newSet = new Item; 
    newSet->hd = new node; 
    newSet->tl = newSet->hd; 
    node *shd = newSet->hd; 
    NodeAddress[n++] = (long) shd; 
    shd->val = a; 
    shd->itemPtr = newSet; 
    shd->next = 0; 
    return (long) newSet; 
} 

template<class T> long ListSet<T>::find (long a) { 
    node *ptr = (node*)a; 
    return (long)(ptr->itemPtr); 
} 

template<class T> void ListSet<T>::Union (long s1, long s2) { 
    //change head pointers in Set s2 
    Item *set2 = (Item*) s2; 
    node *cur = set2->hd; 

    Item *set1 = (Item*) s1; 

    while (cur != 0) { 
     cur->itemPtr = set1; 
     cur = cur->next; 
    } 
    //join the tail of the set to head of the input set 
    (set1->tl)->next = set2->hd; 
    set1->tl = set2->tl; 
    delete set2; 
} 

int main() { 
    ListSet<char> a; 
    long s1, s2, s3, s4; 
    s1 = a.makeset('a'); 
    s2 = a.makeset('b'); 
    s3 = a.makeset('c'); 
    s4 = a.makeset('d'); 
    cout<<s1<<' '<<s2<<' '<<s3<<' '<<s4<<endl; 
    cout<<a.find(NodeAddress[2])<<endl; 
    a.Union(s1, s3); 
    cout<<a.find(NodeAddress[2])<<endl; 
}