---
# System prepended metadata

title: Algo｜Union Find 演算法
tags: [Algo]

---

# Union Find 演算法
- 實作兩個 functions，此版本只有做 path compression
- 如果再加入 rank 概念，可以分析幾乎在 O(1) 做集合查詢、聯集
    - https://zh.wikipedia.org/zh-tw/%E5%B9%B6%E6%9F%A5%E9%9B%86
```c++=
int parent[1000];
void unio(int x, int y){
    int px = find(x);
    int py = find(y);
    if(px!=py)        parent[px] = py;
}
int find(int x){
    if(parent[x]==x)    return x;
    else                return parent[x] = find(parent[x]);
}

int main(void){
    for(int i=0;i<n;i++)    parent[i] = i;
    
    for(...){
        if(find(x)!=find(y)){
            unio(x, y);
            // ...
        }
    }
}
```
- 也可以調整成字串版本
```c++=
unordered_map<string, string> parent;
void unio(string a, string b){
    string pa = find(a);
    string pb = find(b);
    if(pa!=pb)  parent[pa] = pb;
}
string find(string s){
    if(parent[s] == s)  return s;
    return              parent[s] = find(parent[s]);
}
```

