union find 응용문제 풀어보면서 분리집합 개념 재활하기

1. 문제 16562번: 친구비 (acmicpc.net) 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 2. 풀이 어렵게 생각하지 말고.. 먼저 union find 함수를 작성하자 먼저 parent를 찾는 find함수 def find_parent(x,parent): if x != parent[x]: parent[x] = find_parent(parent[x],parent) return parent[x] 다음 union을 수행하는 함수 def ..

• format_list_bulleted 그래프 이론 정복기
• · 2023. 1. 9.
• textsms

union find 최적화 - union by size 배우기

1. 문제 4195번: 친구 네트워크 (acmicpc.net) 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 친구관계인 간선이 주어질때마다 각 사람(노드)에 속한 집합의 크기를 구하는 문제 2. 풀이 이 문제가 어렵게 느껴지는 이유는 일단 노드 수가 주어지지 않는다.. 간선의 수 f만 주어지는데.. 이럴 경우 최대 노드 수는 2f개 일 것이다. 사실 최대 노드 수만 알아도 문제를 푸는데 상관이 없다. 왜냐하면 union이 일어날때마다 각 노드에 속한 집합의 크기만 구하면 되니까 parent = [..

• format_list_bulleted 그래프 이론 정복기
• · 2022. 10. 5.
• textsms