048 이분 그래프

첫번째 코드

 

사실 이분 그래프의 정의는 알았지만 문제와 풀이를 아직 잘 이해하지 못했다.

책을 참고해서 코드를 작성하였다...

천천히 뒷 문제들을 풀면서 이해하고 다시 돌아와야 할 문제이다....

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())
iseven = True

def DFS(x):
    global iseven
    visited[x] = True
    for i in A[x]:
        if not visited[i]:
            check[i] = (check[x] + 1) % 2
            DFS(i)
        elif check[x] == check[i]:
            iseven = False

for _ in range(n):
    v, e = map(int, input().split())
    A = [[] for _ in range(v+1)]
    visited = [False] * (v+1)
    check = [0] * (v+1)
    iseven = True

    for i in range(e):
        start, end = map(int, input().split())
        A[start].append(end)
        A[end].append(start)
    
    for i in range(1, v+1):
        if iseven:
            DFS(i)
        else:
            break
    
    if iseven:
        print("YES")
    else:
        print("NO")

 

통그아아...

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/1707.%E2%80%85%EC%9D%B4%EB%B6%84%E2%80%85%EA%B7%B8%EB%9E%98%ED%94%84

programmers/백준/Gold/1707. 이분 그래프 at main · ornni/programmers