# Union Find

### Description

Union Find是一個演算法, 用來找出node間是否有相連的關係。

包含: 直接相連(a<->b), a,b直接相連, \
&#x20;         間接相連(a<->b<->c), a, c間接相連

&#x20;graph中的node是否相連的關係可使用array or map 表示.

Map\<element,  parent element>

Array\[element]  = Parent element

當某兩個node的parent為同一個即為相連

### Questions

* Find island count
* 著色問題

### Functions

#### Union: 建立graph間 兩node connect的關係&#x20;

#### TimeComplexity: O(N)

```java
public void union(int[] parents, int a, int b) // means a and b is connected
{
    int aRoot = find(parents, a);
    int bRoot = find(parents, b);
    if(aRoot != bRoot){
        parents[bRoot] = aRoot;
    }
}

```

#### Find: 找出 root of the node

#### TimeComplexity: O(N)

root的parent會是root自己。

```java


private int find(int[] parents, int node){
    if(node == parents[node])
        return node;
    else
        return find(parents, parents[node]);
}
```
