집합 계발 식 통합 상세 + C 코드 구현

합병
그리고 집합 을 찾 습 니 다. 이것 은 비교적 간단 한 것 입 니 다. 숲 으로 모 의 집합 을 하고 집합 과 합병 은 두 나무의 합병 입 니 다. 집합 을 찾 는 것 은 특정한 나무의 뿌리 노드 를 찾 는 것 입 니 다.
각종 합병 작업 을 피 할 수 없 기 때문에 특정한 나무의 깊이 가 비교적 클 수 있 고 이에 대응 하 는 경 로 는 압축 되 고 계발 식 합병 이 발생 할 수 있다.
이곳 은 경 로 를 압축 하지 않 는데 주로 이 물건 이 비교적 보급 되 었 고 이해 하기 어렵 지 않다.
그래서 바로 본론 으로 들 어 갑 니 다: 계발 식 합병
계발 식 합병
이 이름 을 처음 봤 는데 유 여 가 의 책 에 놀 랐 습 니 다. 그리고 집 을 찾 아 쓴 지 1 년 이 되 었 습 니 다. 이 계발 식 합병 을 몰 랐 습 니 다. 이어서 보 니 실현 은 rank 배열 을 사 용 했 습 니 다. 원 서 는 이렇게 말 했 습 니 다.
하나의 최 적 화 는 작은 나 무 를 큰 나무 에 합 쳐 깊이 가 크 지 않다 는 것 이다.이 최 적 화 를 계발 식 합병 이 라 고 한다.rank [i] 는 i 의 질 서 를 나타 내 고 질 서 를 이용 하여 방금 언급 한 계발 식 합병 을 대체 합 니 다.
그리고 멍 해 졌어 요. 질 이라는 걸 어떻게 이해 해 요..
그래서 인터넷 에서 찾 아 보 니 많은 블 로그 들 이 책 에서 묘사 한 것 과 거의 똑 같 았 다.
그래서 스스로 이해 할 방법 을 생각 했 는데, 다행히 이해 했다.
배열 rank 의 의미
여기 예 를 들 자.
만약 에 우리 가 이 나무 들 을 하나의 도시 로 본다 면 이런 도시 들 은 발전의 정도 에 따라 서로 다른 등급 으로 나 눌 수 있다. 예 를 들 어 소형 도시, 중형 도시, 대형 도시, 도시 와 도시 간 에 합병 할 수 있 고 소형 도시 와 소형 도시 가 합병 되면 그 중의 한 도 시 는 중형 도시 로 업그레이드 되 고 두 중형 도시 가 합병 된다 고 규정 한다.그 중 한 도 시 는 고급 도시 로 업그레이드 된다.
우 리 는 다시 한 번 더욱 엄밀 한 규칙 을 만 들 었 다.

두 개의 동급 도시 가 합병 되 어야 한 도시 가 업그레이드 할 수 있다

소형 도시 가 대형 도시 에 합병 되 고 대형 도시 가 업그레이드 되 지 않 는 다

등급 이 높 은 도 시 는 등급 이 낮은 도시 로 구성 되 어야 한다

나무 로 돌아 가 -- 이 문제
우 리 는 rank [a] 가 나무 a 의 등급 을 나타 낸다 고 가정 합 니 다. 우선 이렇게 부 르 세 요. 이름 이 라 고 불 러 도 됩 니 다.위의 규칙 (전환) 에 따라 한 그루 의 나무의 등급 이 비교적 높 으 면 이 나무의 '규모' 가 비교적 높 을 것 이다. 즉, 깊이 가 좀 깊 을 것 이다. 예전 의 합병 최적화 규칙 에 따라:
하나의 최 적 화 는 작은 나 무 를 큰 나무 에 합 쳐 깊이 가 크 지 않다 는 것 이다.
등급 이 낮은 나 무 를 등급 이 높 은 나무 에 합 친 것 이다.
총결산
우 리 는 합병 함 수 를 써 야 합 니 다. 이 함 수 는 두 그루 나무의 등급 (rank) 에 따라 어떤 나무 가 다른 나무 로 합 쳐 지 는 지 판단 하고 한 그루 의 나무 가 업그레이드 되 어야 하 는 지 판단 해 야 합 니 다.
코드:

void union_ (int a,int b) {
    int x = find_(a), y = find_(b);
    if (ranks[x] > ranks[y]) {//        ，       
        bcset[y] = x;
    } else {
        bcset[x] = y;
        if (ranks[x] == ranks[y]) {//         ，       
            ranks[y] ++;
        }
    }
}