# Disjoint Sets

###### tags: `演算法`、`資料結構`

*CSRF Exercises 21.2-1*
Write pseudocode for MAKE-SET,FIND-SET,and UNION using the linked-list representation and weighted-union heuristic.Make sure to specify the attributes that you assume for set objects and list objects

Answer:

struct Node{
    Data;
    Set;
    Next;
}

struct Set{
    head;
    tail;
    length;
}
//v is a node
MAKE-SET(v){
    Set s//init a new set
    v.Set=s
    s.head=v
    s.tail=v
    s.length+=1
    return s
}

FIND-SET(v){
    return v.Set
}

UNION(s1,s2){
    if s1.length>s2.length
        SWAP(s1,s2)
    s1.tail.Next=s2.head
    s1.tail=s2.tail
    node=s2.head
    while node!=NULL
        node.set=s1
        node=node.Next
    s1.length+=s2.length
    s2.head=NULL
    s2.tail=NULL
    delete s2
    return s1
}