[662B] Graph Coloring

문제 링크 : http://codeforces.com/problemset/problem/662/B

N개의 정점과 M개의 엣지로 이루어진 그래프(N <= 100,000, M <= 100,000) 가 있는데, 각각의 엣지에는 빨강 혹은 파랑으로 색깔이 부여되어 있다.

이때 각 정점에 대해 그 정점을 선택하면 그 정점과 연결된 엣지의 색이 전부 반대로(빨강->파랑, 파랑->빨강) 변하게 만들 수 있다. 이 때 최소 개수의 정점만 선택해서 모든 엣지의 색을 같게 만들 수 있는 방법을 구하는게 문제.

 생각보다 단순한 방법으로 풀 수있는데, 일단 전체 엣지를 파랑으로 만들지 빨강으로 만들지 정해서 둘 중에 답이 더 작은 걸 답으로 고른다고 하자.

 만약에, 그래프에서 임의의 정점 v1에 대해 그 정점 v1과 v2가 연결되어 있고 색깔은 빨강, 그리고 v1과 v3가 연결되어 있고 색깔은 파랑이라고 하자. 전체 그래프를 빨간색으로 바꾸려고 할 때, 만약 정점 v1을 선택한다면 v2는 반드시 선택해야만 하고, v1을 선택하지 않는다면 v2도 선택하면 안 된다. 왜냐하면, 한 엣지에 연결된 양쪽 정점에 대해 하나만 선택할 경우 색깔이 바뀌고 둘 다 선택하거나 둘 다 선택하지 않을 경우 색깔이 유지되기 때문이다.

반대로 v3의 경우 v1을 선택한다면 v3를 선택해서는 안 되고, v1을 선택하지 않는다면 v3를 선택해야만 한다.

 그러면 이제 그래프에서 아무 정점이나 골라잡아서, 그 정점을 선택할지 선택하지 않을지만 정한다면 그 정점에서 방문할 수 있는 모든 정점에 대해 위 과정을 거쳐 각 정점을 선택해야할 지 선택하면 안 될지가 연쇄적으로 결정된다. 만약 탐색 과정에서 모순이 발생하면(앞서 방문했을 땐 선택해야한다 였는데 다른 정점을 거쳐 도달했더니 선택하면 안 된다로 바뀐 경우), 방법이 없는 케이스다.

 즉 4가지 경우로 나눠서 생각해 볼 수 있는데,

  1. 목표 색깔은 빨강이고 시작 정점 v1을 선택하는 경우

  2. 목표 색깔은 빨강이고 시작 정점 v1을 선택하지 않는 경우

  3. 목표 색깔은 파랑이고 시작 정점 v1을 선택하는 경우

  4. 목표 색깔은 파랑이고 시작 정점 v1을 선택하지 않는 경우

이 중 최솟값을 고르면 된다. 여기서 선택하는 경우 or 선택하지 않는 경우는 더 간단하게 줄일 수 있는데, 시작 정점 v1과 "똑같이 해야하는가" 혹은 "다르게 해야하는가"로 표현하면 한 번만 dfs를 돌려도 된다. 예를 들어 v1과 v2가 빨간 색으로 연결되어 있다면 v1을 선택할 경우 v2도 선택해야하고, v1을 선택하지 않는다면 v2도 선택하지 않아야된다. 즉, v1과 v2는 선택을 하든 선택을 하지 않든 똑같이 따라가야 하는 정점들이다. 이를 이용하면 전체 정점 집합을 v1과 같은 선택을 해야하는가 / 다른 선택을 해야하는가의 두 가지 집합으로 구분할 수 있고 둘 중 더 크기가 작은 쪽의 정점을 모두 선택해주는 경우로 따져주면 된다.

따라서 시간복잡도는 DFS의 시간복잡도와 동일하므로, O(N+M)이 된다.