도전 4 Union-Find

Union-Find 문제는 집합의 파티션을 표현하는 데 사용한다. 집합의 원소를 숫자 0, 1 등으로 표현하고, 각 원소마다 같은 파티션 안의 다른 원소를 부모로 두는 포레스트 데이터 구조로 파티션을 표현한다. 한 파티션 안에 있는 집합들은 그 집합의 루트로 지정된 원소에 의해 구분된다.

여기서 사용하는 두 가지 핵심 연산은 다음과 같다.

• Find: 첫 시작 집합의 원소 하나를 받아서 해당 집합의 루트를 리턴한다.

• Union¹: 원소 두 개를 받아서 각 원소가 속한 두 집합을 하나로 합친다.

포레스트 데이터 구조를 parent란 이름의 타입이 size_t인 인덱스 테이블에 구현할 수 있는가? 이 테이블에서 SIZE_MAX란 값은 여러 트리의 루트를 의미하고, 나머지 숫자는 해당 트리에서 부모의 위치를 나타낸다. 구현하기 전에 parent를 싱글턴 파티션으로 만드는 초기화 함수를 반드시 고려해야 한다. 다시 말해 자기가 속한 집합의 루트를 원소로 갖는 파티션이다.

인덱스 테이블을 이렇게 만들었을 때, 주어진 인덱스에 대해 트리의 루트를 찾는 Find 함수를 구현할 수 있는가?

루트 경로에 나오는 모든 parent 항목을 특정한 값으로 변경하는 FindReplace 함수를 구현할 수 있는가?

모든 parent 항목을 앞서 찾아낸 루트로 변경하는 FindCompress 함수를 구현할 수 있는가?

주어진 두 원소에 대해 각각의 트리를 하나로 합치는 Union 함수를 구현할 수 있는가? 이때 한쪽은 FindCompress 함수를 사용하고, 다른 한쪽은 FindReplace를 사용하도록 만들어야 한다.