원활 한 공사 (및 조사 집합)
코드:
int[] parent = new int[5];
public int findRoot(int x)
{
int r = x;
// root == parent[root]
while (r != parent[r])
r = parent[r];
return r;
}
public void Merge(int x, int y)
{
int p , q;
p = findRoot(x);
q = findRoot(y);
if (p != q) { //
parent[x] = q;
}
}상기 코드 는 기본 기능 을 현실 화 시 켰 기 때문에 우 리 는 최 적 화 를 할 수 있다.최적화 해 야 할 것 은 이 알고리즘 에서 사용 빈도 가 가장 높 은 방법, 즉 루트 노드 를 찾 는 방법 (findRoot) 이다.
1. 높이 가 작은 나 무 를 높이 가 큰 나무 위 에 합 친 코드 에서 두 나 무 는 임의로 합 친 것 입 니 다. 속도 가 더 높 은 것 을 찾기 위해 서 는 나무 전체 가 가능 한 한 균형 을 유지 해 야 합 니 다.두 나무의 높이 가 h1, h2 라 고 가정 하면 합 친 높이 h 는:
2. 경 로 를 압축 하여 루트 노드 (r = parent [r]) 를 찾 고 경로 의 모든 노드 를 수정 하여 루트 노드 를 가리킨다.
최 적 화 된 코드:
int[] parent = new int[5]; // ，
int[] height = new int[5]; //
public int findRoot(int x)
{
int r = x;
while (r != parent[r])
r = parent[r];
int i = x, j;
//
while (i != r)
{
j = parent[i];
parent[i] = r;
i = j;
}
return r;
}
public void Merge(int x, int y)
{
int p , q;
p = findRoot(x);
q = findRoot(y);
if (p != q) {
//
if (height[p] == height[q])
{
parent[p] = q;
height[q]++;
}else if (height[p] > height[q]){
parent[q] = p;
}else {
parent[p] = q;
}
}
}그리고 조사 집 에 대한 상세 한 소 개 는 이 글 을 참조 하 시기 바 랍 니 다.http://blog.csdn.net/dm_vincent/article/details/7655764
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
