유니온 파인드

• 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산, 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘
• 연결 되어 있지 않으면 자기 자신이 대표노드가 되므로, 자기 자신을 저장
• 항상 대표 노드끼리 연결해 준다.
• find 작동 원리
  • 대상 노드 배열에 index값과 value 값이 같은지 확인
  • 다르면 value와 같은 index로 이동
  • index와 value가 같을 때 까지 반복
  • 나오면서 값을 1로 만들어 줘야함
• 유니온 파인드 목적
  • 같은 집합인지 찾는 것
• 중요사항
  • find 구현
    • 값이 들어오면 그 값이 index와 value가 같은지 확인
  • find를 돌아 나오면서 값을 변경하는 경로 압축과정
    • 다르면 그 index위치의 value는 재귀로 find를 돌았을 때 시작노드