유니온 파인드 (Union-Find)

유니온 파인드 (Union-Find)

• 그래프 / 트리의 대표적인 알고리즘
• 서로소인 부분집합의 표현
• 여러 노드가 있을 때, 두 노드가 같은 그래프에 속해있는지 알 수 있음
  • 2개의 원소가 같은 집단(같은 그래프)에 속하는지 판별
• union 함수 : 2개의 서로 다른 노드를 같은 그래프로 합침 (두 노드의 부모를 같은 원소로 만듬)
• find 함수 : 2개의 서로 다른 원소가 같은 그래프에 속하는지 판별

 

유니온 파인트 코드

union

public static void union(int a, int b) {
	a = find(a);
    b = find(b);
    
    if(a != b){
    	parent[b] = a;
    }
}

find

public static int find(int a) {
	if(parent[a] == a)
    	return a;
    else
    	return parent[a] = find(parent[a]);
}