UNION-FIND
MST(크루스칼)
LCA와 응용
[풀이]
전체 풀이를 설명하면 MST를 먼저 만들고, 쓰지 않은 간선들을 하나 하나 탐색해가면서 그 간선을 추가하면 CYCLE이 생긴다. 무조건. 그러므로 CYCLE을 제거할 수 있는 MST의 간선을 하나 제거한다.
그랬을 때 나오는 스패닝 트리의 값의 최솟값을 찾으면 두 번째로 작은 MST의 값을 구할 수 있다.
이제 제거할 간선을 하나 찾아야 하는데, greedy하게 생각해보면 cycle에 있는 간선 중 가장 큰 간선을 제거해야한다. cycle은 lca를 구하면 MST의 cycle을 찾을 수 있다. 문제는 lca까지 가는 간선 중 최댓값을 구해야하는데, naive하게 생각해보면 dfs돌리면 되니 O($n$)이다.
LCA를 구하는 과정에서 LCA의 응용중에 하나인 LCA까지의 경로의 최솟값을 구하는 방법을 이용해서 O($log_2{n}$)으로 줄일 수 있다.
그런데, 이 문제에 처리해줘야할 사항이 두 가지가 있다.
1. MST에 추가되지 않았던 edge를 추가 했을 때, MST의 값과 같다면 그건 두 번째 MST가 아니다.
2. MST가 아예 만들어지지 않는 경우도 있다.
3. 두 번째 MST가 없을 수도 있다.
MST가 아예 안 만들어 지는 경우는 edge 추가마다 cnt를 올려줘서 체크 가능하고, 두 번째 MST가 없는 경우는 $e$ == $v - 1$인 경우 밖에 없다.
까다로운게 첫 번째 case인데, 일반적으로 lca까지의 경로의 최댓값을 찾는 문제로 풀게 될 경우, 똑같은 cost의 edge를 발견하면 그 edge를 제거하려고 하므로 MST의 값을 출력하게 된다.
그래서, maxValue 배열을 update할 때 update되기 전의 값을 second로 저장해두고 update를 한다. 그러면 최댓값과, 그것 보다 작은 두 번째 최댓값을 저장하게 되는데, 이걸 이용해서 maxValue query를 처리할 때, 내가 추가하기로 pick한 edge의 cost와 최댓값이 다른 경우 당연히 최댓값을 보고, 같은 경우는 두 번째 최댓값으로 리턴 해주면 된다.
다시, 전체 알고리즘을 설명하면
1. MST를 만든다.
2. 만든 MST에서 lca와 maxValue를 전처리 해둔다.
3. maxValue전처리할 때 maxValue뿐만 아니라 그것보다 작은 두 번째 최댓값도 같이 update한다.
4. 추가하지 않았던 edge를을 하나하나 추가해보면서, 그 edge를 추가했을 때 만들어지는 cycle에서 maxValue를 찾아서 제거하여 spanningTree를 만들어 result를 update한다.
5. maxValue를 찾을 때, lca를 찾는 알고리즘을 따라가며 찾으며, 만약 maxValue가 추가하려고 하는 edge의 cost와 같다면, (3)에서 전처리 해둔 두 번째 maxValue로 update해준다.
6. 만약, query로 얻어온 maxValue의 값이 -INF인 경우엔 두 번째 MST가 없다는 얘기이므로(추가하려는 edge와 다른 cost의 edge가 없는 경우) -1을 출력한다.
3년 전에 푼 이후 재채점으로 hack당하고 다시 푼 문제인데, 생각보다 까다로웠다. second maxValue로 update해주는 것도 까다로웠고, 예외사항중 MST가 아예 안 만들어지는 경우를 고려하지 않아서 여러번 틀렸다.
그래도 덕분에 3년전 그 당시 lca알고리즘을 정확히 공부하다기 보다는 이런게 있구나~ 하고 template만 만들어놓고 가져다 넣는 식으로 했었는데, 완벽히 이해해서 이제 손으로 직접 짤 수 있게 되어 의미 있는 문제였다.
