FIND
-
[백준]1717: 집합의 표현 - JAVA문제풀이/백준 2021. 5. 2. 14:48
[백준]1717: 집합의 표현 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 풀이 문제도 간결하고 읽어보면 알 수 있듯이 union-find문제이다. union-find는 MST의 Kruskal알고리즘에서도 사용되는 이론이므로 꼭 알고있자. 풀이도 간단하다. 0을 입력받으면 union, 1을 입력받으면 각 요소의 부모가 같은지 확인후 yes, no를 출력해주면 된다. union함수는 각 요소들의 부모를 같게 만들어 ..