유니온 파인드란?
•
유니온 파인드는 그래프 알고리즘이다.
•
두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다.
•
노드를 합치는 Union 연산과 루트 노드를 찾는 Find 연산으로 이루어진다.
구현
•
2 개의 method 와 한개의 init
•
init
for (int i = 0; i <= n; i++) {
parent[i] = i;
}
Java
복사
•
find
int find(int node) {
if (parent[node] == node) {
return;
}
return find(int parent[node]); // => 고도화 대상
}
// 고도화 : find 함수 쓰면서 parent 갱신
int find(int node) {
if (parent[node] == node) {
return;
}
int ret = find(parent[node])
prent[node] = ret // 갱신
return parent[node];
}
Java
복사
•
merge