[Python] 백준 1717: 집합의 표현 - disjoint set (Union find)

문제 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 �� www.acmicpc.net 풀이 처음엔 문제에서 설명하는 순서대로 인접리스트를 만들고, set으로 풀었는데 메모리 초과가 났다. 따라서 disjoint set을 사용해서 풀어야하는데 루트배열을 두고 서로 루트가 같으면 같은 집합에 속해있는것으로 판단하면 된다. 먼저 n의 크기의 root 배열을 만들고, i(본인)로 채운다. i 0 1 2 3 4 5 6 7 root[i] 0 1 2 3 4 5 6 7 그 후 a, b 두 집합을 합치기 위해서는 a의 ..
PS/Python 2020. 9. 16. 04:07
1