이 문제는 그래프에서 각 간선이 제외되었을 때마다 최소비용신장트리(Minimum cost Spanning Tree, MST)의 비용을 구하는 문제이다.가장 쉬운 방법은 모든 M개의 간선에 대해 그 간선을 제외한 그래프를 만들고 Kruskal Algorithm O(M logM)을 통해 MST를 구하는 방법이다. 이 방법은 O(M^2 log M)의 시간복잡도를 가지며 부분문제2를 해결하여 23점을 받을 수 있다.
주어진 그래프의 MST를 구하면 MST에 포함되지 않는 간선들을 제외한 그래프의 MST는 그대로이기 때문에 새로 MST를 구하지 않아도 된다. 이를 통해 MST에 포함된 N-1 개의 간선에 대해서만 MST를 구하면 되고,O(NM logM)의 시간복잡도로 부분문제3을 해결하여 34점을 받을 수 있다.
MST에 있는 간선이 제외되는 경우 위의 방법처럼 MST를 다시 구하지 않고도 해당 간선이 어떤 다른 간선으로 대체되어야 하는지를 아래의 방법으로 빠르게 구할 수 있다.
주어진 그래프의 MST를 트리 T 라 하자. T 에 있는 간선 e가 제외되고 새로운 MST T' 을 구하는 상황이다. T 에서 간선 e를 제외하면, 두 개의 트리로 나누어진다. 이제 원래 그래프에서 나누어진 두 트리를 연결하는 간선 중 가중치가 제일 작은 것을 구해 연결을 해주면 새로운 MST T′을 구할 수 있다. 이 때 나누어진 두 트리를 연결하는 간선 중 가중치가 제일 작은 것을 빠르게 구할 수 있도록 해야 한다.
원래 그래프에 있는 간선이며 T 에 있지 않은 간선 x가 있다. 이 간선은 노드 v1�卵� 노드 v2 를 연결하는 간선이다. 이 간선이 T 에서 간선 e가 제외되었을 때, 나누어지는 두 트리를 연결하는 간선이 되기 위해서는 필요충분으로 T 에서 노드 v1 에서 노드 v2 로 가는 경로 중 에 간선 e가 있어야한다.
이를 이용하여 MST T 에 속하지 않은 그래프의 간선 x에 대해서 T 에서 노드 v1 에서 노드 v2 로 가는 경로에 가중치 값을 기록하여 빠르게 구할 수 있다. v1 과 v2 사이의 경로는 T에서 v1 과 v2 의 Least Common Ancestor(LCA) p를 구했을 때 v1 ~ p ~ v2이다. 이 방법 의 시간복잡도는 O(MN) 이며, 부분문제4를 해결하여 61점을 받을 수 있다.
부분문제4를 해결하는 O(MN) 방법을 개선하면 O(M log M) 에 해결이 가능하다. MST T에 포함되지 않은 간선 x에 대해 MST T에서 v1 과 v2 를 연결하는 경로 v1 ~ p , v2 ~ p 에 가중치 값을 기록하는 과정을 모든 간선 x에 대해 반복하게 된다. 이를 가중치가 작은 간선 x부터 수행하면 이미 가중치가 기록된 MST T의 간선은 건너 뛸 수 있다. 가중치 기록을 반복하지 않고 건너뛰는 처리를 Union Find Algorithm(혹은 서로소집합 구조, Disjoint Set data structure)의 경로 압축(Path Compression)과 같은 과정을 통하여 해결할 수 있다.