'유니온파인드' 태그의 글 목록

2606 바이러스 문제는 "유니온 파인드" 를 이용하여 해결할 수 있다. https://www.acmicpc.net/problem/2606

알고리즘/백준 2018. 4. 20. 23:00

유니온 파인드 상호 배타적 집합이라고도 한다. 2가지 연산으로 이루어져 있다. 1. Find: x가 어떤 집합에 포함되어 있는지 찾는 연산2. Union: x와 y가 퐇마되어 있는 집합을 합치는 연산- 구현은 트리를 이용해서 한다. - parent[i] = i 의 parent 가 저장되어 있음 * parent[] 배열을 각자 자기 번호로 초기화 하는 것에 주의** find 연산에서 결과를 가지고 있다가 저장하고 반환하는 것에 주의 *** 이 union, find 연산은 MST의 크루스칼 알고리즘에 사용된다. https://www.acmicpc.net/problem/1717