이분 그래프 (백준 1707)

이분그래프

모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프

이분 그래프인지 확인하는 방법

너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)을 이용 → 서로 인접한 정점이 같은 색이면 이분 그래프 X
1. BFS, DFS로 탐색하면서 정점을 방문할 때마다 두 가지 색 중 하나를 칠한다.
2. 다음 정점을 방문하면서 자신과 인접한 정점은 자신과 다른 색으로 칠한다.
3. 탐색을 진행할 때 자신과 인접한 정점의 색이 자신과 동일하면 이분 그래프가 아니다.
4. BFS의 경우 정점을 방문하다가 만약 같은 레벨에서 정점을 다른 색으로 칠해야 한다면 무조건 이분 그래프가 아니다.

 

모든 정점을 다 방문했는데 위와 같은 경우가 없다면 이분 그래프이다.

※ 이때 주의할 점은 연결 그래프와 비연결 그래프를 둘 다 고려 해야한다는 것이다.
그래프가 비연결 그래프인 경우 모든 정점에 대해서 확인하는 작업이 필요하다.

참고: https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html

 

---

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

1707번: 이분 그래프

이분 그래프 예시

from collections import deque
import sys

input = sys.stdin.readline
k = int(input())

def bfs(start):
    visited[start] = 1
    q = deque()
    q.append(start)
    while q:
        a = q.popleft()
        for i in graph[a]:
            if visited[i] == 0:
                visited[i] = -visited[a] # i와 연결된 정점을 -로 바꿔줌 (이분그래프)
                q.append(i)
            else:
                if visited[i] == visited[a]:
                    return False
    return True

for i in range(k):
    v, e = map(int, input().split())
    flag = True
    graph = [[] for i in range(v + 1)]
    visited = [0 for i in range(v + 1)]
    
    for j in range(e):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
        
    for k in range(1, v + 1):
        if visited[k] == 0:
            if not bfs(k):
                flag = False
                break

    print("YES" if flag else "NO")