문제

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

나의 코드

"""
1. 아이디어


2. 시간복잡도

"""

from collections import deque
from sys import stdin
input = stdin.readline

# 이분 그래프 탐색 : 각 노드가 인접한 노드들과 다른 값을 가지고 있으면서, 총 2가지 값으로 다 표현할 수 있는 그래프
def bfs(v):
    visited[v] = 1
    q = deque([v])

    while q:
        node = q.popleft() # 현재 노드를 꺼낸다.

        for i in graph[node]:
            if visited[i] == 0: # 만약 현재 노드와 연결된 노드를 방문한 적이 없다면
                visited[i] = -visited[node] # 현재 값과 구별될 수 있도록 값을 입력 해준다.
                q.append(i)
            else: # 만약 현재 노드와 연결된 노드를 방문한 적이 있다면
                if visited[i] == visited[node]: # 만약 연결된 노드가 같은 값을 가지고 있다면 이분 그래프 조건에 어긋난다.
                    return False
                
    return True

T = int(input())

for _ in range(T):
    v, e = map(int, input().split())
    graph = [ [] for _ in range(v+1) ]
    visited = [0] * (v+1)
    flag = True

    for _ in range(e):
        v1, v2 = map(int, input().split())
        graph[v1].append(v2)
        graph[v2].append(v1)

    for i in range(1, v+1):
        if visited[i] == 0: # ★ 이게 필요한 이유가 한번의 bfs로 전부 -1 또는 1값이 업데이트 되는게 아니기 때문에 필요하다. (두번째 풀때 안쓰다가 틀림) ★
            if not bfs(i): # False가 반환되면 "NO"가 출력될 수 있게 flag를 조정한다.
                flag = False
                break

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

느낀점

다음 그림의 흐름대로 작성하면 된다.
여기서 핵심은 이분 그래프 탐색하는 방법을 떠올리는 것과 이분 그래프의 조건을 알고 있는 것이다.

그림 참고자료

https://vixxcode.tistory.com/24