[그래프] 이분 그래프

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때 이분 그래프라고 한다 

DFS나 BFS를 활용하여 인접한 노드들은 다른 색으로 칠해가다가 이미 같은 색인 경우 이분 그래프로 만들 수 없음을 알 수 있다 

 

[관련 문제]

1707 이분그래프

https://www.acmicpc.net/problem/1707

 

13265 색칠하기 

https://www.acmicpc.net/problem/13265

 

1953 팀배분

각각 싫어하는 사람들의 정보가 주어짐 (서로 같은 팀을 하기 싫어하는 사람들)

-> 연결된 정점을 다른 색으로 칠한다 

https://www.acmicpc.net/problem/1953