[정리] Union And Find

유니온파인드

• 그래프 알고리즘이며, 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다.
• 서로소 집합, 상호 베타적 집합으로 불린다.

구현

package UnionFind;

public class UnionFind {
    static int[] parent = new int[10];
    static int find(int val){
        if(val == parent[val])
            return val;
        else
            return parent[val] = find(parent[val]);
    }
    static void union(int p,int c){
        p = find(p);
        c = find(c);
        if(p!=c)
            parent[c] = p;
    }

    /**
     * 1 : 1
     * 2 : 2
     * union(1,2) -> 1 : 1, 2 : 1
     * 3 : 3
     * union(2,3) -> find(3) -> 3, find(2) parent[2] -> 1;
     *  -> 3 : 1
     * @param args
     */
    public static void main(String[] args) {
        for(int i = 1;i<=9;i++){
            parent[i] = i;
        }
        union(1,2);
        union(2,3);
        union(4,5);
        union(5,6);
        union(7,8);
        union(3,9);
//        count boundary -?

        for(int i : parent)
            System.out.println(i);
    }
}