DisjointSet
-
[백준] Python - 집합의 표현개발/알고리즘 2022. 3. 24. 13:10
1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net DisJoint Set과 Union-Find에 대해 공부하기 위해서 새로 문제를 선택했다. DisJoint Set은 서로소 집합 또는 분리 집합이라고 한다. 자식이 자신의 부모를 가리키는 형태로 존재하고 집합 간의 교집합은 존재하지 않는다. 이 문제의 경우 Union과 Find를 구현하는 기본적인 문제이다. 입력으로 주어진 값에 따라 합집합을 수행할 것인지 값을 찾을 것인지 선택한다. Union의 경우 합치려는 두 대상의..