BOJ - 1707

백준 문제 링크
이분 그래프

❓접근법

1. 이분 그래프는 그래프의 정점을 두 가지 색으로 칠할 때,
   인접한 정점은 다른 색을 가진 그래프이다.
   
2. visited에 3가지 값을 줌으로써 구분할 수 있다.
   0 : 아직 방문하지 않은 곳, 1 : RED, 2 : BLUE

👌🏻코드

from collections import deque

def bfs(graph, x):
    
    queue = deque()
    queue.append(x)
    
    if visited[x] == 0: # 방문하지 않았다면 처음엔 1로 지정
        visited[x] = 1
        
    while queue:
        now = queue.popleft()
        
        color = visited[now] # 현재의 색깔
        
        for i in graph[now]:
            if visited[i] == 0: # 방문하지 않았을 때
                queue.append(i) # 큐에 넣어서 탐색
                if color == 1:
                    visited[i] = 2
                else:
                    visited[i] = 1
                    
            elif visited[i] == 1: # 방문했는데 색깔이 1일 때
                if color == 1:
                    return False
                
            elif visited[i] == 2: # 방문했는데 색깔이 2일 때
                if color == 2: 
                    return False
                
    return True

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    
    graph = [[] for _ in range(n + 1)]
    
    visited = [0] * (n + 1)
    
    for _ in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
        
    flag = True
    
    for i in range(1, n + 1):
        if bfs(graph, i) == False:
            flag = False # 현재 노드와 인접한 노드가 색깔이 같을 때
            break
            
    if flag == True:
        print('YES')
    else:
        print('NO')