====== 2색 색칠 ======

  * 인접한 두 노드는 다른 색을 갖도록 하면서, 전체 노드들을 2가지 색으로 색칠하기. 
  * 일반적인 vertex k-coloring 은 NP라서 PS에서는 다룰일이 별로 없다.


===== 기본정리 =====
  * 2색 색칠이 가능하다 <=> 이분그래프이다
  * 그래프에 홀수길이 사이클이 없으면 2색 색칠 가능
    * 트리는 사이클이 아예 없으니 당연히 가능

===== 알고리즘 =====
  * 기본적으로는 그래프를 순회하면서 컬러를 지정하면 된다. 시간복잡도는 O(V+E)
  * [[ps:Disjoint Set]]을 사용하는 방법도 가능하긴 하다. 
    * BFS에 비해 느리다. 
    * 하지만, incremental 하게 관리해야 할 필요가 있는 경우에는 이 방법이 필요하다
    * 코드는 [[ps:problems:boj:7535]] 참고
  * [[ps:2-sat]]으로 모델링해서 푸는 방법도 가능하다. 
    * 이건 disjoint set을 쓰는것보다도 더욱 느릴것 같기는 하다.
    * 하지만 문제에 변형이 복잡하게 주어지면, 이렇게 모델링하는게 간단할수도 있을것 같긴 하다 (아직 본적은 없다)

==== 구현 ====
  * 보통은 2-colorable 한지(=이분그래프인지) 여부를 찾는 태스크가 실제 coloring을 요구하는 태스크보다 더 흔하기는 하다. 그래서 is_bipartite 와 같은 함수를 따로 만드는 것도 생각해봤지만, 기각.
  * 방문처리를 color를 주는것으로 처리하기 때문에, DFS나 BFS나 코드가 stack을 쓰느냐 queue를 쓰느냐를 제외하고는 그냥 똑같다. 속도는 BFS가 살짝 더 빨랐다.
  * DFS는 이런식
    * <dkpr py>
def two_coloring(graph):
    color = [None] * len(graph)
    for source in range(len(graph)):
        if color[source] is not None:
            continue
        stack = [source]
        color[source] = True
        while stack:
            u = stack.pop()
            color_u = color[u]
            for v in graph[u]:
                if color[v] is None:
                    color[v] = not color_u
                    stack.append(v)
                elif color[v] == color_u:
                    raise ValueError('Not bipartite graph')
    return color
</dkpr>
  * BFS는 이런식
    * <dkpr py>
def two_coloring(graph: Graph) -> list[bool]:
    color = [None] * len(graph)
    for source in range(len(graph)):
        if color[source] is not None:
            continue
        color[source] = True
        queue = collections.deque([source])
        while queue:
            u = queue.popleft()
            col_u = color[u]
            for v in graph[u]:
                if color[v] is None:
                    color[v] = not col_u
                    queue.append(v)
                elif color[v] == col_u:
                    raise ValueError(
                        'Graph is not 2-colorable (not bipartite).'
                    )
    return color
</dkpr>


==== 코드 ====
  * [[:ps:teflib:graph#two_coloring|teflib.graph.two_coloring]]  

==== 관련 문제 ====
  * [[ps:problems:boj:1707]]: N≤20,000, M≤200,000
  * [[ps:problems:boj:12893]]: N≤2,000, M≤1,000,000
  * [[ps:problems:boj:7535]]: N≤2,000, M≤1,000,000