[E] Clearing Up

트리에는 간선이 n-1개 있으므로, n이 홀수면 답이 존재하지 않는다. 주어진 그래프에서 S-간선만 전부 다 제거해보자. M-간선으로 이루어진 컴포넌트들이 생길 것이다. 컴포넌트의 개수를 K라고 하자. 전체 그래프가 연결되기 위해선 K-1 개의 S-간선이 필요하다. 따라서 K-1 > (n-1)/2 라면 답이 존재하지 않는다. 전체 그래프를 연결하기 위해 필요한 K-1 개의 S-간선 집합을 구하자. 그리고 K-1 < (n-1)/2 인 경우에는 집합의 원소 개수가 (n-1)/2 이 될 때 까지 S-간선을 추가하는데, 집합에 있던 간선과 cycle을 이루지 않도록 추가한다. 집합의 원소를 (n-1)/2 개로 만들 수 없으면 답이 존재하지 않는다. 이렇게 만든 S-간선 집합만으로 그래프를 다시 만든다. 여기에 M-간선 (n-1)/2 개를 cycle이 생기지 않도록 추가하면 된다. 역시 이 경우도, 이렇게 만들 수 없으면 답이 존재하지 않는다. 위에서 간선 집합을 구하거나 간선을 추가할 때는 kruskal 알고리즘과 비슷한 방식으로 작업하면 된다. 위 알고리즘은 왜 올바른가? 일단 K-1 개의 S-간선을 찾는 이유는 자명하다. 이렇게 찾은 K-1 개의 S-간선 집합만으로 그래프를 만든다. 그리고 K개의 컴포넌트마다 각각 M-간선으로 스패닝트리를 만든다. 매 스텝마다 S-간선을 아무거나 하나 골라 추가해도 다음과 같이 조작하면 전체 그래프가 스패닝트리가 되도록 할 수 있다. (단, S-간선 끼리 cycle을 이루는 경우는 당연히 배제해야함) 1) 추가된 S-간선이 특정한 M-간선 컴포넌트 안에 속하는 경우 -> M-간선 스패닝트리의 M-간선을 하나 제거한 후 S-간선으로 교체하여 여전히 스패닝트리가 되도록 할 수 있다. 2) 추가된 S-간선이 서로다른 M-간선 컴포넌트를 연결하는 경우 -> 연결된 두개의 M-간선 컴포넌트 안에 속한 M-간선 하나를 아무거나 제거하면 된다. 따라서 S-간선이 (n-1)/2 개가 될 때까지 아무거나 추가해도 답을 만들 수 있다.