서로소 집합2 유니온-파인드(Union-Find), 서로소 집합(Disjoint Set) Union Find와 Disjoint Set은 동일한 의미를 가지며, 여러 서로소 집합의 정보를 저장하고 있는 자료구조를 의미합니다. 트리 형태로 구현되며, 보통 자신의 root 노드를 집합을 구분하는 ID처럼 사용된다. 이 자료구조는 두 가지 연산을 지원한다. 1. find(p): p의 root 노드의 값을 가져옴 2. union(p, q): p와 q의 집합을 합친다. (코드 구성 시에는 union이라는 예약어가 있어 merge로 대체) 맨 처음에는 모든 노드가 자기 스스로를 root 노드로 가지게 된다. find 함수는 현재 자기의 parent 노드가 자신이면 자기를 반환하고, 아니면 자신의 parent 노드의 parent노드를 반환한다. 이러한 방식으로 자신의 root 노드를 찾게 된다. union.. 2020. 4. 14. [BOJ 1717] 집합의 표현 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a www.acmicpc.net 위 문제는 n + 1개의 집합을 서로 합치고, 특정 원소가 같은 집합인지를 확인하는 문제이다. 이는 Union-Find 구조를 이용하.. 2020. 4. 8. 이전 1 다음
