Union Find

Description

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

包含: 直接相連(a<->b), a,b直接相連, 間接相連(a<->b<->c), a, c間接相連

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

Map<element, parent element>

Array[element] = Parent element

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

Questions

• Find island count

• 著色問題

Functions

Union: 建立graph間 兩node connect的關係

TimeComplexity: O(N)

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自己。

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