문제 파악부터 시작 1. 초기에 n+1개의 집합을 이루고 있다. 2. 여기에 합집합 연산과 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산하려한다. 딱봐도 유니온-파인드 알고리즘을 떠올리게끔 만든 문제. 두 원소를 통해 인자가 2개라는 거 파악하고 같은 집합에 포함되어 있는지 확인하려면? find함수를 재귀로 돌려서 노드를 찾고, union 함수로 같으면 반환하고 다르면 합치기

현재 노드들이 같은 그룹에 속해 있는 지~ 같은 그룹으로 합치고 싶을 때! 쓰는 알고리즘이다. #find 1. par 배열은 각 노드의 부모를 담아놓는다. 2. par 배열의 index는 각 노드의 번호이고 그 값은 부모 노드를 의미한다. 처음 모든 노드의 값을 -1이라고 한다. find 함수는 재귀적으로 자신의 부모의 부모를 탐색한다. 부모가 없는 노드를 발견하면 최상위 노드로 볼 수 있다. 최상위 노드를 찾았다면 해당 노드의 값을 리턴한다. 그 이전의 노드들은 최상위 노드의 번호로 자신의 부모 노드를 갱신한다. #union 두 노드를 인자로 받아서 같은 그룹인지 확인하려하는 알고리즘이다. find 함수를 통해서 해당 노드의 부모 노드를 확인한다. 위 함수에서는 인자로 받은 a,b변수에 부모의 노드의 ..