블로그 옮겼습니다
Union-find 다른 말로 Disjoint sets(상호 배타적 집합) 이란 여러개의 집합들에 대해,서로 다른 두 집합의 교집합이 공집합이며, 모든 집합들의 합집합이 전체 집합이 되는 집합들을 말한다.그런데 이게 유용한 이유는 이렇다. 1. 서로 다른 두 원소가 같은 집합 내에 속해 있는지, 아니면 서로 다른 집합에 속해있는 지를 빠른 시간내에 구할 수가 있다.2. 서로 다른 집합에 속해있는 두 노드가 속해있는 두 집합을 빠른시간에 합쳐 더 큰 하나의 집합으로 만들 수가 있다. 그렇기 때문에 크루스칼 알고리즘에서도 유용하며, dfs 대용으로도 쓸 수가 있으며 그 활용이 무궁무진하다.그런데 일반적인 방법으로는 집합을 한꺼번에 합치는 것은 가능하지만, 집합 내의 특정 한 원소 단위로는옮길 수가 없다. 하..
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3138 정말 좋은 문제인것 같다. 풀이
https://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&page=show_problem&category=&problem=4075 해석이 너무 안돼서 제대로 이해하는데 엄청 오래걸렸다.. \(5\leq{N}\leq{2\cdot{10^4}}\)\(0\leq{M}\leq{2\cdot{10^5}}\)N은 회사의 수, M은 쿼리의 수N개의 회사는 각각 센터를 가지고 있다. 이 회사들의 일부를 병합을 하여 하나의 더 큰 덩어리로 만드는 동시에센터는 하나로 유지를 하려고 한다. 병합을 할 때에는 하나의 덩어리의 센터에서 나머지 덩어리의 아무 회사로도로를 놓으면서 병합을 한다. 도로의 길이는 회사 a와 b를 이을 때 | a - b| mod 10..