백준 1717
1) 백준 1717 : 집합의 표현 (https://www.acmicpc.net/problem/1717)
Union Find.
1 <= n <= 1,000,000까지의 수가 입력 될 수 있다.
따라서 총 n+1개의 부분집합이 생긴다.
이들의 포함 관계를 알기 위해서 길이가 n개인 배열을 생성한 후, 자기 자신을 가리키도록 초기화한다.
(arr[1] = 1, arr[2] = 2 ... arr[i] = i /i번째 value = i 이도록)
이후 0 operation이 들어와서 합집합을 만드려고 한다면(unite) 자신의 소속을 찾은 후(=findParent)
하나의 것(=소속, arr[a])을 다른 하나의 것(=소속, arr[b])으로 바꾼다.
(순서는 중요하지 않다. 결국 하나의 집합은 하나의 수를 가지게 되기 때문이다).
문제의 예시를 보면
input > 0 1 3
index = 0 1 2 3 4 5 6 7 8 9
arr[] = 0 3 2 3 4 5 6 7 8 9
input > 0 7 6
index = 0 1 2 3 4 5 6 7 8 9
arr[] = 0 3 2 3 4 5 6 6 8 9
input > 0 3 7
index = 0 1 2 3 4 5 6 7 8 9
arr[] = 0 3 2 6 4 5 6 6 8 9
<arr[1]이 아직도 3으로 남아있는데, 이후에 findParent를 하면 recursive하게 돌면서 arr[1]도 6으로 바꿔서 계산하기 때문에 괜찮다>
findParent는 자신의 index와 소속이 같다면 그 수를 리턴하고 그렇지 않다면 또 부모(=소속, arr[i])를 호출하며 재귀적으로 돈다.
*그리고 cin은 느려서 통과가 안되니 scanf를 씁시다
https://github.com/JangJuMan/2019-winter-PS/blob/master/8_1717.cpp
끗
