union-find5 [알고리즘] 분리 집합(Union-Find) 1. 개요 1. 각 노드들을 그룹을 지을 때 사용하는 알고리즘 2. 알고리즘 코드 int parent[MAX_G]; int Find(int a) { int pA = parent[a]; if (pA == a) return a; return parent[a] = Find(pA); } void Union(int a, int b) { int pA = Find(a); int pB = Find(b); if (pA 2024. 4. 14. [백준 C++] 20303번: 할로윈의 양아치 1. 문제 https://www.acmicpc.net/problem/20303 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 2. 알고리즘 분류 다이나믹 프로그래밍 자료 구조 그래프 이론 그래프 탐색 분리 집합 배낭 문제 3. 소스 코드 #include #include #include using namespace std; int N, M, K; int candy[30001]; int total_candy[30001]; int.. 2024. 4. 3. [백준 C++] 20040번: 사이클 게임 1. 문제 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 2. 알고리즘 분류 자료 구조 분리 집합 3. 소스 코드 Key Point) 1. 사이클 여부를 확인하는 문제는 Union-Find를 활용한다. 2. a와 b의 parent가 같으면, 사이클이다. #include using namespace std; int parent[500005]; int Find(int a) { if (a == parent[a]) return a; else r.. 2023. 10. 2. [백준 C++] 1647번: 도시 분할 계획 1. 문제 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 2. 알고리즘 분류 그래프 이론 최소 스패팅트리 3. 소스 코드 #include #include #include #include using namespace std; int N, M, ans, max_cost; int parent[100005]; vector edges; int Find(int x) { if (parent[x] == x) return.. 2023. 9. 12. [백준 C++] 1197번: 최소 스패닝 트리 1. 문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 2. 알고리즘 분류 그래프 이론 최소 스패닝 트리 3. 소스 코드 #include #include #include #include using namespace std; int parent[10005]; bool is_cycle; vector graph; // 부모를 찾는 함수 int find_parent(int x) { if (parent[.. 2023. 6. 10. 이전 1 다음
