python 은 간단 한 검색 집합 을 실현 합 니 다.

그리고 집합 은 트 리 형 데이터 구조 로 서로 교차 하지 않 는 집합 과 조회 문 제 를 처리 하 는 데 사용 된다.항상 사용 중 에 숲 으로 표시 한다.
그리고 세 가지 기본 적 인 조작 을 조사 하여 뿌리 노드 를 얻 고 두 노드 가 연결 되 는 지 판단 하 며 연결 되 지 않 는 노드 를 연결 하 는 것 (두 노드 각자 의 집합 을 합병 하 는 것 과 같다)
유 니 온 Find 클래스 로 하 나 를 표시 하고 집합 을 찾 습 니 다. 구조 함수 에서 배열 parent 를 초기 화 합 니 다. parent [i] 는 색인 이 i 인 노드 이 고 직접적인 부모 노드 는 parent [i] 입 니 다.초기 화 할 때 각 노드 가 연결 되 지 않 기 때문에 parent [i] = i 를 초기 화하 여 자신 을 자신의 부모 노드 로 만 들 고 각 노드 가 서로 연결 되 지 않도록 합 니 다.

    def __init__(self, n):
        self.parent = list(range(n))

parent [i] 는 자신의 직접 부모 노드 만 표시 하기 때문에 두 노드 가 교차 하 는 지 확인 하려 면 그들의 뿌리 노드 가 같 는 지 비교 해 야 합 니 다.따라서 자신의 루트 노드 를 조회 하 는 방법 을 봉인 해 야 한다.

    def get_root(self, i):
        while i != self.parent[i]:
            i = self.parent[i]

        return i

다음은 뿌리 노드 가 같 는 지 비교 함으로써 두 노드 가 연결 되 는 지 여 부 를 판단 할 수 있다.

    def is_connected(self, i, j):
        return self.get_root(i) == self.get_root(j)

두 노드 를 연결 하려 면 그 중의 한 노드 의 루트 노드 의 parent 를 다른 노드 의 루트 노드 로 설정 해 야 합 니 다.주의 하 세 요. 두 노드 를 연결 하 는 것 은 두 노드 자체 만 연결 시 키 는 것 이 아니 라 실제 적 으로 그들 이 속 한 집합 을 합병 시 키 는 것 입 니 다.

    def union(self, i, j):
        i_root = self.get_root(i)
        j_root = self.get_root(j)
        self.parent[i_root] = j_root

다음 에 우 리 는 두 개의 작은 최 적 화 를 한다.get 호출 때문에루트 는 자신의 직접적인 부모 노드 를 계속 찾 아서 뿌리 노드 를 찾 아야 합 니 다. 만약 에 이 나무의 등급 이 너무 깊 으 면 성능 에 심각 한 영향 을 받 을 수 있 습 니 다.그래서 우 리 는 유 니 온 에 있 을 때 가능 한 한 합병 후의 나무의 높이 를 줄 여야 한다.구조 함수 에 배열 rank 을 새로 만 듭 니 다. rank [i] 는 노드 i 가 있 는 집합 트 리 의 높이 를 표시 합 니 다.
따라서 트 리 를 합 칠 때 노드 i 와 노드 j 의 루트 i 를 각각 획득 합 니 다.루트 와 j루트 이후, 우 리 는 rank [i root] 와 rank [j root] 를 방문 하여 두 나무의 높이 를 비교 하고, 높이 가 비교적 작은 그 나 무 를 높이 가 높 은 그 나무 에 연결 합 니 다.높이 가 같 으 면 마음대로 rank 값 을 1 로 추가 할 수 있 습 니 다.

    def union(self, i, j):
        i_root = self.get_root(i)
        j_root = self.get_root(j)

        if self.rank[i_root] == self.rank[j_root]:
            self.parent[i_root] = j_root
            self.rank[j_root] += 1
        elif self.rank[i_root] > self.rank[j_root]:
            self.parent[j_root] = i_root
        else:
            self.parent[i_root] = j_root

유 니 온 작업 에 대한 개량 을 통 해 나무의 높이 가 너무 높 은 것 을 방지 할 수 있다.우 리 는 get루트 작업 자 체 를 최적화 합 니 다.현재 매번 get 실행루트 를 찾 으 려 면 부모 노드 를 층 층 이 찾 아야 합 니 다. 시간 이 많이 걸 립 니 다.뿌리 노드 에 부모 노드 가 없고 글 의 시작 부분 에서 만약 에 한 노드 가 부모 노드 가 없다 면 그의 부모 노드 는 바로 자신 이기 때문에 뿌리 노드 의 부모 노드 만 자신 이 라 고 할 수 있다.현재 우 리 는 하나의 판단 을 더 해서 현재 노드 의 부모 노드 가 뿌리 노드 인지 판단 한다. 만약 에 뿌리 노드 가 아니라면 자신의 부모 노드 를 뿌리 노드 로 설정 하고 마지막 에 자신의 부모 노드 로 돌아간다.

    def get_root(self, i):
        if self.parent[i] != self.parent[self.parent[i]]:
            self.parent[i] = self.get_root(self.parent[i])
        return self.parent[i]

이상 은 python 이 간단 하고 집합 을 찾 는 방식 입 니 다.