[백준][DFS/DP] 1707. 이분 그래프 (파이썬/Python)

<BFS>

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

def bfs(start):
    visited[start] = 1
    q = deque()
    q.append(start)
    while q:
        x = q.popleft()
        for i in graph[x]:
            if visited[i] == 0:
                visited[i] = -visited[x]
                q.append(i)
            else:
                if visited[i] == visited[x]:
                    return False
    return True



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

    for _ in range(e):
        a, b = map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)
    for i in range(1,v+1):
        if visited[i] == 0:
            if not bfs(i):
                bipartite = False
                break
    print("YES" if bipartite else "NO")

 

<DFS>

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

def dfs(v, group):
    visited[v] = group 
    for i in graph[v]:
        if visited[i] == 0: # 
            if not dfs(i, -group):
                return False
        elif visited[i] == visited[v]:
            return False
    return True

for _ in range(int(input())):
    V, E = map(int, input().split())
    graph = [[] for i in range(V+1)] 
    visited = [0] * (V+1) 

    for _ in range(E):
        a,b = map(int, input().split())
        graph[a].append(b) 
        graph[b].append(a) 

    bipatite = True

    for i in range(1, V+1):
        if visited[i] == 0:
            bipatite = dfs(i, 1)
            if not bipatite:
                break

    print('YES' if bipatite else 'NO')