---
tags: 演算法
title: 並查集
---
## 並查集
### 目標
> 判斷連通 , 找兩個點有沒有在同個集合裡面 ( 有同個father,血緣關係 )

### 實作
> 準備一個 陣列 存根節點 並把根結點 設為自己
>
>製作兩個 funtion
> - 查找 Find
> - 合併 Union

> 透過查找是否屬於同個 "根" 相不相同 就可以知道關係
### 優化?
> 因為 無腦的合併 會出現 很長一條鏈 -> 在搜尋的時候就會非常花時間
> 解決方法:
> - 紀錄每集合的高度 -> 把矮的樹 並到 高的樹裡面 (有點像在幫樹做平衡)
> - 每次查找的時候 把結果再存回去
### Pseudocode:

vector<int> f,Rank;   // f存根節點 Rank存高度

void UFinit(int V){
    f.resize(V+1);  
    Rank.resize(V+1);
    for(int i=0;i<=V;i++)
        f[i] = i;
}

int Find(int x){
    return x == f[x] ? x : f[x] = Find(f[x]);
}

void Union(int x,int y){
    if (Rank[x] < Rank[y])
        pa[x] = y;
    else{
        if (Rank[x] == Rank[y])
            Rank[x]++;
        pa[y] = x;
    }
}

### 應用:
>Kruskal 算法