유니온파인드

[baekjoon 21924] 도시 건설 (최소 스패닝 트리, 크루스칼, 유니온파인드) (C++)

https://www.acmicpc.net/problem/21924 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net 일반적인 최소 스패닝 트리를 찾는 문제였다. 하지만 문제를 제대로 안 읽고 급하게 푸느라 바로 정답을 맞히진 못했고 몇 가지 놓친 사항들이 있었다. 1. 수의 범위 (건물의 개수는 10^5개고, 도로의 비용은 최대 10^6이다.) 즉, int의 범위를 넘어간다. 2. 문제의 ..

[baekjoon 20040] 사이클 게임 (유니온 파인드, union-find) (C++)

www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 유니온 파인드를 통해 사이클 판별을 하는 문제이다. 두 개의 정수가 주어지고, 그 둘은 연결되는데 선분들이 연결되다가 사이클이 발생할 때를 출력한다. 사이클이 생성되지 않을 경우 0을 출력. #include using namespace std; int parent[500001], n, m, from, to, answer; int getParent(int x) { if (parent[x] == x) retu..