2-coloring problem

N개의 정점을 빨간색(1) 또는 파란색(0)으로 칠하려고 한다.

다음과 같은 제약이 M개 주어질 때 모든 정점을 색칠하는 방법이 존재하는지 판단해보자.

• 1 u v: 정점 u와 정점 v는 서로 다른 색으로 칠하여야 한다.
• 2 u v: 정점 u와 정점 v는 동일한 색으로 칠하여야 한다.

세 가지 풀이를 소개한다.

 

1. DFS or BFS

모든 제약에 대하여 정점 u와 v를 잇는 무향 가중치 간선을 구성하자.

이때 가중치는 1번 제약의 경우 1로, 2번 제약의 경우 0으로 설정한다.

각 정점 u에 연결된 모든 간선 e = (v, w)에 대하여 정점 v는 ((정점 u의 색) ^ w)로 칠하면 된다.

 

2. Union-Find 1

1번 제약의 경우 u와 v + N, 그리고 u + N과 v를 병합한다.

2번 제약의 경우 u와 v, 그리고 u + N과 v + N을 병합한다.

각 정점 u에 대하여 u와 u + N이 서로 다른 집합에 속한다면 제약을 만족하는 해가 존재한다.

 

3. Union-Find 2

우선 모든 2번 제약에 대하여 u와 v를 병합한다.

그리고 모든 1번 제약에 대하여 root(u)와 root(v)를 잇는 무향 간선을 구성하자.

그 다음 각 정점 u에 대하여 인접한 모든 정점 {v_1, v_2, ..., v_k}를 하나의 집합으로 병합한다(v_i와 v_j를 병합).

각 정점 u에 대하여 인접한 정점 v가 서로 다른 집합에 속한다면 제약을 만족하는 해가 존재한다.

 

끝

끝