-
먼저 N이 3인 경우와 N이 4이상인 경우로 구분하자.
N=3 일때에는, 블루/레드가 모두 끊겨있거나, 블루/레드가 모두 연결되어있는 경우는 불가능하다. 만들수 있는 상태는 (1,0)이나 (0,1) 뿐이다. N이 작으므로, 만드는 방법은 간단히 찾을수 있다.
N>=4 일때에는, 우선 블루/레드가 모두 끊겨있는 것은 불가능하다. 한쪽이 끊기면 다른쪽은 연결되게 되어있다. 따라서 만들어야 하는 상태가 (0,1)이나 (1,0)이어서 한 색깔이 끊어져야 하는데 현재 그 색깔이 연결되어있는 경우에는, 그 색깔을 끊는데만 주력하면 된다. 그 색깔을 끊으면 다른 색깔은 자연적으로 연결된다.
만들어야 하는 상태가 (1,1)인 경우일때는 또 복잡하다. 현재 상태가 레드가 끊어져있는 상태라고 가정하자. 생각할수 있는 방법은 레드 그래프에서 연결된 컴포넌트들을 찾은다음, 컴포넌트들을 연결하는 레드 엣지를 추가하는 것이다. 컴포넌트가 n개라면 n-1의 엣지만을 추가해서 레드 그래프를 모두 연결시켜줄수 있다.
그런데.. 이 과정에서 블루 그래프가 끊기는 경우가 없는지를 생각해봐야 한다. 여기에 해당되는 유일한 경우는, 레드 그래프에서 어떤 1개의 노드 u만 따로 떨어져 있고 나머지 V-1개의 노드들은 연결되어 있을때, u를 다른 노드 v와 연결시켰더니, v와 다른 노드들 사이에 블루 엣지가 없어지는 경우이다. 즉, v가 처음에 블루엣지 1개와 레드엣지 V-2 개를 갖고 있는 상황이다. u를 연결시켜줄 노드 v를 찾을때, 아무 노드나 찾지 말고 레드 엣지의 갯수가 V-2 보다 작은 노드 v를 찾아서 연결해주면 블루 그래프가 끊기는 일 없이 1개의 엣지만 추가해서 레드 그래프를 연결해줄수 있다.
하지만 이게 끝이 아니다. V-1개의 노드들이 완전그래프를 이루어서, 모든 노드들이 레드엣지를 V-2개씩 들고 있는 경우가 있을수도 있다. 이때는 누구와 연결시켜도 그 노드는 블루 연결이 끊어지게 된다. 그래서 추가적으로 레드엣지를 블루엣지로 한번 더 바꿔줘야한다. 이 경우에는 (u,v)를 레드로 바꿔주고 (v,w) 를 블루로 바꿔주면 원하는 상태로 만들어줄 수 있다.
케이스웍이 복잡하긴 하지만, 시간복잡도가 많이 큰 작업은 아니다. 총 시간복잡도는 global mincut를 구하는 O(V^3)에 바운드된다.