<style>
html, body, .ui-content {
background: #222222;
color: #00BFFF;
}
/* 設定 code 模板 */
.markdown-body code,
.markdown-body tt {
background-color: #ffffff36;
}
.markdown-body .highlight pre,
.markdown-body pre {
color: #ddd;
background-color: #00000036;
}
.hljs-tag {
color: #ddd;
}
.token.operator {
background-color: transparent;
}

</style>

###### tags: `Data Structure`

# Disjoint Set
### <a href="https://hackmd.io/@CLKO/rkRVS_o-4?type=view">資料來源</a>

## 尋找源頭

vector<char> char_list;//紀錄源頭的vector
int find_root(int a){
    if(char_list[a] - 'a' == a)//自己的源頭為自己
        return a;
    char_list[a] = find_root(char_list[a] - 'a') + 'a';//尋找源頭
    return char_list[a] - 'a';
}

## 將兩個集合合併

void UNION(int a, int b){
    int roota = find_root(a);
    int rootb = find_root(b);
    if(rootb < roota)//源頭較小的值
        char_list[roota] = rootb + 'a';//比較大的值的源頭設成比較小的值的源頭
    else
        char_list[rootb] = roota + 'a';
    return;
}

# Disjoint Set Union-find algorithm (DSU) 並查集

class DSU{
public:
    DSU(int n) : parent(n){
        for(int i=0; i < n; i++){
            parent[i] = i;
        }
    }
    int findParent(int x){
        if(parent[x] == x)
            return x;
        return parent[x] = findParent(parent[x]);
    }
    void UNION(int x, int y){
        int parentx = findParent(x), parenty = findParent(y);
        if(parentx == parenty)
            return;
        parent[parenty] = parent[parentx];
        return;
    }
    vector<int> parent;
};