[백준] 1707 - 이분 그래프 (파이썬, Python)

https://pixabay.com/ko/photos/우산-햇빛-여자-비-빛-6239364/

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

1707번: 이분 그래프

 

전체 코드

제출 언어: PyPy3

시간: 1216ms

 

from collections import deque
import sys

def bfs(adj_list):
    global adj_mat, type_arr
    que = deque([(v, 1) for v in adj_list])

    while que:
        cv, ct = que.popleft()

        type_arr[cv] = ct
        adj_list = adj_mat[cv]

        for nv in adj_list:
            if type_arr[nv] == -1:
                que.append((nv, (ct+1)%2))

            elif type_arr[nv] == ct:
                return False
                
    return True

if __name__ == "__main__":
    K = int(sys.stdin.readline().strip())
    answer_list =[]

    for _ in range(K):
        V, E = map(int, sys.stdin.readline().strip().split())

        adj_mat = [ [] for _ in range(V) ]
        type_arr = [-1] * V
        is_success = True

        for _ in range(E):
            v1, v2 = map(int, sys.stdin.readline().strip().split())

            adj_mat[v1-1].append(v2-1)
            adj_mat[v2-1].append(v1-1)

        for v1 in range(V):
            if type_arr[v1] != -1:
                continue
                
            type_arr[v1] = 0
            adj_list = adj_mat[v1]

            if len(adj_list) > 0:
                is_success = bfs(adj_list)

                if not is_success:
                    break
            
        answer = "YES" if is_success else "NO"
        answer_list.append(answer)

    for a in answer_list:
        print(a)

---

읽어 주셔서 감사합니다 :)

틀린 부분이 있다면 댓글로 편히 알려주세요😊