# bipartite(이분그래프) 확인하기
어떤 그래프 내에서 인접한 두 정점이 서로 다른 2개의 부류에 소속되어 있을 때 그 그래프를 이분그래프(bipartite)라고 한다. 인접한 두 정점은 같은 부류에 포함되어 있으면 안된다. 아래의 그래프에서 정점들을 빨간색과 초록색 2가지로 분류했을 때, 각 정점은 자신과 인접한 정점과 다른 색을 가지고 있으므로 이분그래프라고 할 수 있다.
아래의 그래프도 이분그래프에 속한다.
어떤 그래프가 이분그래프인지 아닌지 판별하려면, 어떤 정점 `v`의 부류와 `v`와 인접한 정점의 부류가 같은지 확인하면 된다. 위 예시의 경우, 정점 `v`의 색깔과 `v`와 인접한 정점의 색깔이 같은지 여부를 확인하면 되는 것이다.
어떤 그래프가 이분그래프인지 아닌지 확인하는 함수 `bipartite()`를 구현하면 아래와 같다.
```python
def bipartite(n, adjacent_list, start, end):
color = [-1 for _ in range(n)]
queue = list()
queue.append(start)
color[start] = BLACK
while queue:
v = queue.pop(0)
for adj_v in adjacent_list[v]:
if color[adj_v] == -1:
color[adj_v] = WHITE if color[v] == BLACK else BLACK
queue.append(adj_v)
else:
if color[adj_v] == color[v]:
return 0
return 1
```
`queue`를 확인하는 `while`문은 정점의 갯수만큼 실행되며, 각 정점에 의해 `while`문이 1번 실행되었을 때 `for`문은 그 정점이 가진 간선의 갯수만큼 실행되므로 시간복잡도는 `O(|V| + |E|)`이다.
이미지 출처
*
* [위키백과 - 이분그래프](https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84)
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://kde6260.gitbook.io/dev/algorithm-quiz/bipartite.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.