[백준][Python] 1707번 이분 그래프

DFS 풀이

import sys
sys.setrecursionlimit(1000000)

def dfs(v,node):
    
    global visited
    global graph
    visited[v] = node
    
    for i in graph[v]:
        
        if visited[i] == 0:
    
            dfs(i,-node)        

k = int(input())

for _ in range(k):
    
    n,m = map(int,sys.stdin.readline().split())
    graph = [[] for i in range(n+1)]
    visited = [0] * (n+1)
    for i in range(m):
        node1,node2 = map(int,sys.stdin.readline().split())
        graph[node1].append(node2)
        graph[node2].append(node1)
    
    for i in range(1, n + 1):
        if visited[i] == 0:
            dfs(i,1)
    
    for i in range(1, n + 1):
        if visited[i] == 0:
            dfs(i,1)
    
    result = True
    for i in range(1,n+1):
        for j in graph[i]:
            
            if visited[i] == visited[j] * -1:
                result = True
            else :
                result = False
                break
        if result ==False :
            break
    
    if result == True:
        print("YES")
    else :
        print("NO")

BFS 풀이

from collections import deque
import sys

def bfs(v):
    
    queue = deque()
    queue.append(v)
    visited[v] = 1
    
    while queue :

        v = queue.popleft()

        for i in graph[v]:
            
            if visited[i] == 0 :
                
                queue.append(i)
                visited[i] = -visited[v]

k = int(input())
for _ in range(k):
    n,m = map(int,sys.stdin.readline().split())
    graph = [[] for i in range(n+1)]
    visited = [0] * (n+1)
    for i in range(m):
        node1,node2 = map(int,sys.stdin.readline().split())
        graph[node1].append(node2)
        graph[node2].append(node1)
                       
    for i in range(1,n+1):
        if visited[i] == 0 :
            bfs(i)
    
    result = True
    for i in range(1,n+1):
        for j in graph[i]:
                
            if visited[i] == visited[j] * -1:
                result = True
            else :
                result = False
                break
        if result ==False :
            break
        
    if result == True:
        print("YES")
    else :
        print("NO")