그리고 입문 및 예제 분석 을 수집 합 니 다.

1. 병 집 된 원리
그리고 집합 (Union - Find) 은 트 리 형 데이터 구조 로 서로 교차 하지 않 는 집합 과 조회 문 제 를 처리 하 는 데 사용 된다.주로 두 가지 조작 과 관련된다. 합병 과 찾기.구체 적 으로 말 하면 초기 상태 에서 집중 적 인 요 소 는 서로 교차 하지 않 고 일련의 조작 (Union) 을 거 친 후에 하나의 집합 으로 합 쳐 진다.그리고 어떤 합병 을 한 후에 특정한 두 요소 가 같은 집합 에 있 는 지 알 고 싶다 면?이 럴 때 는 찾기 (Find) 작업 이 필요 합 니 다.강호 해설 도 는 다음 과 같다.
쉽게 말 하면 이 과정 은 조상 을 찾 고 조상 을 알 아 보 는 이야기 로 이해 할 수 있다.이때 양 좌 사의 관리 자 를 찾 으 려 면 집 구 조 를 사용 하고 조사 할 수 있다. 송 원 교 를 장 무기 문 파 에 귀속 시 키 려 면 집 구 조 를 사용 하고 조사 할 수 있다.그렇다면 수집 의 초기 와 구 조 는 어 떨 까?
2. 수집 한 데이터 구조 와 실현 방식
1. 구축 및 초기 화 및 검색 집합
구 조 를 초기 화하 고 조사 하 는 것 은 위의 그림 에서 볼 때 먼저 몇 명의 강호 인사 가 있 었 던 다음 에 그들 이 모두 각자 의 관리자 라 는 것 을 묵인 하 는 것 이다.코드 는 다음 과 같 습 니 다:

class findUnionCollection{
    private int[] s; //         
    int count; //     
 
 
//                
    public findUnionCollection(int length){
        s = new int[length];
        s = initCollection(s);
        count = length;
    }
 //                   （      －１）
    private int[] initCollection(int[] target){
        for (int i =0;i

각 파 의 집합 이 있 으 니, 이때 우 리 는 각 파 의 관리 자 를 찾 을 수 있 는 방법 을 찾 아야 한다.
코드 설명:

public int find(int x){
 
 //              ０，  －１，        ，    
        if(s[x]<0){
            return x;
        }
  //     ０，                   
  //               ，          
        return find(s[x]);
    }

물론 여기 최적화 점 이 있 는데 바로 우리 쪽 은 이 문 파 의 관리자 에 게 만 관심 을 가지 고 이 문 파 의 각 차원 의 관계 에 관심 을 가지 지 않 는 다 는 것 이다.그래서 저희 가 조회 할 때 이 층 을 관리자 에 게 직접 안내 하고 다음 에 직접 찾 을 수 있 습 니 다. 용 어 는 경로 압축 이 라 고 부 릅 니 다.코드 는 다음 과 같 습 니 다:

public int find(int x){
 
 //              ０，  －１，        ，    
        if(s[x]<0){
            return x;
        }
  //     ０，                   
  //               ，          
      //                 （        ）
        return s[x] = find(s[x]);
    }

조상 을 찾 는 방법 이 있 으 면 당연히 조상 을 알 아 보 는 방법 도 빠 질 수 없다. 강호 의 말 을 바 꾸 는 것 은 바로 다른 파벌 에 의탁 하 는 것 이다.
코드 분석:

//             
public void unionCollection(int child1,int child2){
 
//                ，   ，    ，    
        if(find(child1)==find(child2)){
            return;
        }
//                        
//             ，                ，      （ １）
//   child1    child2    ，  child2      child1   
          if(s[find(child1)]

3. 예제 실전
1. 제목 설명
반 에는 N 명의 학생 이 있다.그 중 어떤 사람 은 친구 이 고, 어떤 사람 은 그렇지 않다.그들의 우정 은 전달 성 을 가지 고 있다.A 는 B 의 친구 이 고 B 는 C 의 친구 라 는 것 을 알 고 있다 면 우 리 는 A 도 C 의 친구 라 고 생각 할 수 있다.이른바 친구 권 이란 모든 친구 의 집합 을 가리킨다.
N * N 의 행렬 M 을 지정 하여 학급 중 학생 간 의 친구 관 계 를 나타 낸다.만약 Mi = 1 은 i 번 째 와 j 번 째 학생 이 서로 친구 관 계 를 가 진 다 는 것 을 알 고 있 음 을 나타 낸다. 그렇지 않 으 면 모른다.너 는 모든 학생 들 이 이미 알 고 있 는 친구 권 의 총 수 를 출력 해 야 한다.
예시 1:
입력:
[[1,1,0],
[1,1,0],
[0,0,1]]
출력: 2
설명: 이미 알 고 있 는 학생 0 과 학생 1 은 서로 친구 이 고 그들 은 한 친구 권 에 있다.
두 번 째 학생 은 스스로 친구 권 에 있다.그래서
예시 2:
입력:
[[1,1,0],
[1,1,1],
[0,1,1]]
출력: 1
설명: 이미 알 고 있 는 학생 0 과 학생 1 은 서로 친구 이 고 학생 1 과 학생 2 는 서로 친구 이기 때문에 학생 0 과 학생 2 도 친구 이기 때문에 그들 세 사람 은 한 친구 권 에서 1 로 돌아간다.
주의:
N 은 [1, 200] 범위 내 에 있다.
모든 학생 에 게 는 Mi = 1 이 있 습 니 다.
Mi = 1 이 있 으 면 MJ = 1 이 있 습 니 다.
2. 문제 풀이 사고
1) 먼저 길이 가 N 인 그룹 을 구축 하고 초기 화 합 니 다. 이때 친구 권 의 수량 이 초기 길이 입 니 다.
2) M 2 차원 배열 을 옮 겨 다 니 며 각 학생 간 의 관계 가 1 인 지 를 판단 하고 1 인 경우 합병 작업 을 통 해 이들 을 연결 시 키 는 동시에 친구 권 의 수량 을 감소 시킨다.
3) 다 옮 겨 다 니 면 친구 권 으로 돌아 가 는 수량.
3. 코드 인 스 턴 스:

class findUnionCollection{
    private int[] s; //         
    int count; //     
 
 
//                
    public findUnionCollection(int length){
        s = new int[length];
        s = initCollection(s);
        count = length;
    }
 //                   （      －１）
    private int[] initCollection(int[] target){
        for (int i =0;i

다음으로 전송:https://juejin.im/post/5cfb87e351882529c549ad51