본문 바로가기

유니온파인드6

Union Find (=disjoint set) 필요한 것: uf배열. find 함수 : 1. uf 배열이 -1로 초기화된 경우 2. uf 배열이자기자신으로 초기화된 경우 merge 함수: 1. merge함수가 일반적으로 union의 기능만을 수행하는 경우 2. MST등에서 union에 성공했을 떄 true, 실패했을 때 false 반환하는 경우 3. merge 후 대표정점(집합)에 포함된 요소의 크기를 초기화해주는 경우 등등등.. 상황에 맞게 구현할 수 있다 int uf[MAX]; //uf배열이 -1로 초기화된 경우 int find(int a) { if (uf[a] == -1) return a; return uf[a] = find(uf[a]); } //union기능만 수행 void merge(int a, int b) { a = find(a); b =.. 2019. 8. 18.
BOJ 16562 - 친구비 https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10,000, 1 ≤ i ≤ N) 다음 M개의 줄에는 숫자 v, w가 주어진다. 이것은 학생 v와 학생 w가 서로 친구라는 뜻이다. www.acmicpc.net 유니온파인드 문제다. 각 집합의 최소를 모두 더한 합을 출력하면 된다. #include #include using namespace std; int n, m, k; int uf[10001]; int cost.. 2019. 8. 6.

티스토리툴바