문제 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 풀이 유니온 파인드(Union-Find)를 활용한 문제다. 0으로 시작하는 입력은 두 집합을 합치는 합집합(Union) 연산을 수행하고, 1로 시작하는 입력은 두 원소가 같은 집합에 속하는지 확인한다. 유니온 파인드란 각 노드가 어떤 집합에 속하는지 판별하는 알고리즘이다. 이를 배열을 이용해 구현하는데 초기에는 배열의 각 요소에는 자신을 가리키도록 한다. Union 연산을 수행할 때는 배열의 값을 루트 노드의 값으로 변..