(출처 : https://www.acmicpc.net/problem/1707)

이분그래프 개념

이런식으로, 첫 정점에서 하나씩 탐색해 나가며 색을 바꿔가며 칠했을 때, 같은 색끼리는 간선이 없는 경우, 이분 그래프라고 함/ 각 정점을 칠할 수 있는 색(빨간색, 파란색)이 있을 때, 인접한 두 정점을 반드시 다른 색으로 칠할 수 있는가?

틀린 코드 - 왜 틀렸는지 못 찾음

import sys
from collections import deque

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

for i in range(k):
    #정점, 간선 개수 받기
    v, e = map(int, sys.stdin.readline().split())

    #인접 정점 넣어주는 중첩리스트
    table = [[] for i in range(v+1)]
    #빨강(=1)인지 파랑(=2)인지 표시하는 리스트
    color=[0]*(v+1)

    #table 완성
    for j in range(e):
        a, b = map(int, sys.stdin.readline().split())
        table[a].append(b)
        table[b].append(a)

    #이분 리스트가 아닐때 멈춰줄 변수
    no=0

    #1부터 정점모두 본인과 본인이랑 인접한 정점의 색깔 정해주기
    for l in range(1, v+1):
        if no == 1:
            break;
        #l과 인접한 정점들을 담을 queue
        queue=deque([])
        if color[l]==0:
            # 색깔 없는 정점은 빨강으로 설정
            color[l]=1

        for item in table[l]:
            queue.append(item)
        l_color = color[l]  # l_color : 현재 색(시작 정점의 색)
        if l_color==1:
            diff_color=2 # diff_color : 현재 색 기준 다른 색
        else:
            diff_color=1

        while queue and no==0:
            q = queue.popleft()
            #color[l]과 color[q]가 같은 색이면 NO
            if l_color==color[q]:
                no=1
                break;
            else:
                if color[q]==0:
                    color[q]=diff_color
    if no == 1:
        print("NO")
    else:
        print("YES")

맞는 코드

(출처 : https://suri78.tistory.com/125)

예슬님 코드

import sys

K = int(sys.stdin.readline())

def bfs(v, visited, color):
    q = [v]
    visited[v] = True
    color[v] = 1 #색깔은 1또는 2
    while q:
        now = q.pop(0)
        for nxt in adj_lst[now]:
            if not visited[nxt]:
                q.append(nxt)
                color[nxt] = 3 - color[now]
                visited[nxt] = True
            else:
                if color[now] == color[nxt]:
                    return False
    return True


for _ in range(K):
    V, E = map(int, sys.stdin.readline().split())
    adj_lst = [[] for _ in range(V + 1)]
    visited = [False for _ in range(V + 1)]
    color = [0 for _ in range(V+1)]
    flag = True
    for _ in range(E):
        a, b = map(int, sys.stdin.readline().split())
        adj_lst[a].append(b)
        adj_lst[b].append(a)
    for node in range(1, V + 1):
        if not visited[node]: #아직 색깔이 정해지지 않은 노드 중
            if not bfs(node, visited, color): #bfs()는 인접한 노드 색깔 같을때 0 return 함
                flag = False #즉, 인접한 노드 색깔 같을 때 flag가 0됨 --> no 출력해야함
                break
    if flag == False:
        print("NO")
    else:
        print("YES")