특이하게 Union Find하는 문제들

Union Find는 그래프에서 간선이 차례대로 생겨날 때, 두 정점이 같은 component에 있는지 판별하는 쿼리를 $O(logN)$에 해결하는 알고리즘이다. 흔히 사용하는 방법으로는 경로 압축과 랭크 비교가 있다. 이러한 방법으로 Union Find를 하면 component를 깊이가 작은 트리 형태로 관리하게 된다. 그런데 component를 특이한 형태로 관리하면 다른 종류의 쿼리들을 풀 수 있게 된다. 

---

2019 FunctionCup의 갈라파고스 여행(island) (https://oj.uz/problem/view/FXCUP4_island)을 풀어보자. 다음과 같은 쿼리를 해결해야 한다.

간선들에 0 ~ M-1의 번호가 붙여져있는 그래프가 있다. 정점 A[i]에서 정점 B[i]까지 이동할 때, 사용하는 간선들의 번호의 최댓값을 최솟값은?

이는 $O(MlogN+QlogN)$에 해결할 수 있다. 각 component를 선형으로 관리하는 방법을 살펴보자.

번호가 작은 간선부터 하나씩 추가하자. 0~i번 간선이 존재하는 상황에서, 같은 component에 있는 정점들은 i번 이하의 간선들을 이용해 이동할 수 있고, 다른 component에 있는 정점들은 i 초과의 간선을 이용해야만 이동할 수 있다. 여기에 u[i+1]과 v[i+1]을 잇는 간선인 i+1번 간선을 추가하자.

1. u[i+1]과 v[i+1]이 같은 component에 있는 경우 : 그 간선은 필요하지 않다. 

2. u[i+1]과 v[i+1]이 서로 다른 component에 있는 경우 : u[i+1]이 속한 component를 A, v[i+1]이 속한 component를 B라 하자. 굳이 u[i+1]과 v[i+1]을 연결하지 않고, A의 임의의 정점과 B의 임의의 정점 사이를 연결해도 된다. 

선형인 두 component를 연결할 때, 끝점끼리 이으면 선형이 유지된다. 따라서 모든 component가 선형이 되도록 연결할 수 있다. 각 component를 linked list처럼 관리하거나,vector와 같은 자료구조를 사용하되 크기가 작은 component를 큰 component에 합쳐주면(small to large) $O(logN)$에 해결할 수 있다. 갈라파고스 여행 문제를 풀기 위해서는 선형으로 Union Find를 한 후 RMQ 쿼리를 해결하면 된다.

---

2018 IOI의 werewolf(늑대인간) (https://oj.uz/problem/view/IOI18_werewolf)를 풀어보자. 이 문제에서는 다음과 같은 뭐리를 해결해야 한다.

정점들에 0 ~ N-1의 번호가 붙여져있는 그래프가 있다. 번호가 L[i] 이상인 정점들만을 이용해 이동할 때 S[i]에서 갈 수 있는 정점들의 집합을 생각하자. 번호가 R[i] 이하인 정점들만을 이용해 이동할 때 E[i]에서 갈 수 있는 정점들의 집합을 생각하자. 두 집합에 교집합이 존재하는가?

S[i]에서 갈 수 있는 정점들의 집합과 E[i]에서 갈 수 있는 정점들의 집합을 구하면 된다. 두 가지 풀이가 존재한다. 두 풀이 모두 갈 수 있는 정점의 집합을 구간으로 나타내는데, 그 과정에서 Union Find를 선형으로 하느냐 heap으로 하느냐의 차이다. 시간복잡도는 둘 다 $O(MlogN+QlogN)$이다.

 

1. 에지로 가중치를 옮긴 후 component를 선형으로 관리한다.

u[i]와 v[i]를 연결하는 간선에 max(u[i], v[i])의 가중치를 적는다. 이 경우 갈라파고스 여행 문제와 똑같이 풀 수 있다. S를 위한 그래프와 E를 위한 그래프 두 가지를 만들면 선형 그래프 2개를 얻을 수 있다. 구하고자 하는 집합은 각각에서 구간이 되고, segment tree 등을 이용하면 그 구간을 $O(logN)$에 구할 수 있다. 교집합을 구하기 위해서는 각 정점을 2차원 평면에 나타내면 된다. 두 그래프에서의 번호(선형 그래프에서 몇 번째인지)를 (x, y) 꼴로 나타내면 N개의 점이 찍힌 평면을 생각할 수 있다. 교집합은 그 평면에서의 직사각형 구간이므로 fenwick tree 등을 이용하면 $O(logN)$에 해결할 수 있다. (online이면 PST로 $O(logN)$에 해결 가능)

 

2. component를 heap으로 관리한다.

번호가 큰 정점부터 추가하자. 정점이 추가되면 그에 연결된 간선들도 생겨나게 된다. 그 과정에서 서로 다른 component들이 합쳐질 것이다. 이 때, 그 component(min heap)의 루트와 새로운 정점을 연결하면 된다. 그러면 새로운 정점을 루트로 하는 min heap이 된다. 이제 S번 정점에서 갈 수 있는 정점들의 집합을 생각하자. S에서 heap의 루트 쪽으로 점점 이동할 경우, 번호가 L[i]보다 작아지는 순간이 생긴다. L[i] 이상인 가장 높은 조상을 u라 하자. u의 subtree에 있는 정점들은 번호가 모두 u보다 크다. 따라서 그 subtree는 모두 S[i]에서 갈 수 있다. 즉, S[i]에서 갈 수 있는 구간이 하나의 subtree가 되는 것이다. subtree를 구간으로 표현하는 방법에는 dfs ordering이 있다. 이 방법을 사용하면 1번 방법과 마찬가지로 평면 쿼리를 통해 해결할 수 있다. 자세한 내용은 https://blog.myungwoo.kr/124 참고. 나는 갈 수 있는 구간(subtree)을 구할 때 sparse table을 이용해서 공간복잡도가 $O(NlogN)$이었다. 그러나 이는 Euler tour를 잘 이용하면 $O(N)$으로 줄일 수 있다.