17171 [ALGORITHM] 백준 1717 - 집합의 표현 (Weighted Union Find) https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net Weighted Union Find란? par과 rank배열을 각기 사용하게 된다면 메모리 공간을 rank배열만큼 더 잡아먹으므로 그를 줄이기 위해 par의 음수의 절대값은 rank배열의 용도로 사용하는 것. (루트노드가 자기 자신을 가르키는 대신 음수를 가지게 함) 단순 Union Find와의 차이 각각의 부모를 저장하는 par배열을 자기 자신의 값이 아.. 2022. 10. 7. 이전 1 다음
